그래프 탐색 알고리즘(dfs, bfs)

1. 사전에 알아야 할 개념들

(1) 그래프

: 여러 개쳬(노드)들이 연결된 그물망

(2) 탐색

: 여러 개체(노드)들 중에서 원하는 개체(노드)를 찾는 과정

2. DFS(depth firsh search)

: 그래프 탐색 알고리즘 중 하나로 깊이 우선 탐색이라고 한다.

깊이 우선 탐색을 쉽게 이해하기 위해서 하나의 예시를 가져오겠다.

예시)

A는 오늘 파리바케트에서 여러 종류의 빵들을 사왔다.

집에 와서 맛있는 빵을 남겨두고 나머지 빵들을 '하나하나씩 차례대로' 다 먹은 다음에 마지막으로 맛있는 빵을 먹었다.

여기서 a가 빵을 먹는 방법이 깊이 우선 탐색이다.

 

아직까지 잘 이해가 안될 것이다. 그래서 다른 예시를 준비해왔다.

 

예시2)

A는 오늘 열심히 일을 하고 집에 와서 넷플릭스를 켰다. A는 넷플릭스의 영화나 드라마들 여러개들 다 챙겨 보지 않고 한 드라마를 몰아서 보았다.

여기서 A가 영화나 드라마를 보는 방식이 깊이 우선 탐색이다.

이를 그림으로 나타낸다면 다음과 같다.

<그림>

 

3.BFS(breath first search)

:그래프 탐색 알고리즘 중 하나로 너비 우선 탐색이라고 한다.

예시)

A는 오늘 파리바케트에서 여러 종류의 빵들을 사왔다.

집에 와서 A는 1번 빵 2번 빵 ... 자신이 좋아하는 빵까지 '동시에' 먹어가면서 자신이 좋아하는 빵을 포함한 빵들을 다 먹었다.

예시2)

A는 오늘 열심히 일을 하고 집에 와서 넷플릭스를 켰다. A는 넷플릭스의 영화나 드라마를 여러개를 다 챙겨 보았다.

이때 A가 빵을 먹는 방식, 영화나 드라마를 보는 방식이 너비 우선 탐색이다.

이를 그림으로 나타낸다면 다음과 같다.

<그림>