[알고리즘] 너비 우선 탐색 (Breadth-first search, BFS)

너비 우선 탐색(Breadth-first search, BFS)

① 너비 우선 탐색이란?

▷ 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.

▷ 프림의 최소 스패닝 트리 알고리즘 등이 너비 우선 탐색을 골격으로 하고 있습니다.

▷ 위의 그림을 너비 우선 탐색을 사용하면 H0(단계) -》 H1(단계) -》H2(단계) 순으로 방문합니다.

▷ k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k입니다. (H0(단계) : 0단계,  H1(단계) : 1단계, H2(단계) : 2단계)

▷ 최단거리는 이동하는 데 필요한 최소 개수의 간선으로 보면됩니다.

▷ 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해 둔 뒤, 모든 인접 정점을 검사한 후 방문하게 됩니다.

▶ 너비 우선 탐색 구현할 경우 : 큐(Queue)의 성질 활용(목록에 먼저 넣은 정점을 항상 먼저 꺼낸다.)

    ※ DFS : 스택(Stack), BFS : 큐(Queue) 를 사용합니다.

▷ 큐에 넣을 때 방문했다고 체크해야 한다. (discovered[])

② 너비 우선 탐색으로 그래프 순회

1번 노드부터 시작하겠습니다.

▷현재 정점 : 1

▷순서 : 1

▷큐 : 1

1번 노드와 인접한 2번,3번 노드 큐에 담깁니다.

▷현재 정점 : 1

▷순서 : 1 2 3

▷큐 : 1 2 3

2번 노드와 인접한 4번,5번 노드 큐에 담깁니다.

▷현재 정점 : 2

▷순서 : 1 2 3 4 5

▷큐 : 2 3 4 5

3번 노드와 인접한 6번,7번 노드 큐에 담깁니다.

▷현재 정점 : 3

▷순서 : 1 2 3 4 5 6 7

▷큐 : 3 4 5 6 7

3번 코드를 큐에서 꺼낸 후 다음으로 거리가 먼 4,5,6,7 노드 순으로 탐색이 이루어집니다.

③ BFS 관련 알고리즘 문제

※ 코드 보기를 누르시면 제가 해결한 코드를 보실 수 있습니다.

(백준 2178) 미로 탐색 (https://www.acmicpc.net/problem/2178) [설명] ▷ (1,1)에서 (N,M) 으로 가는 가장 빠른 길을 구하는 문제 ▷ DFS 탐색으로는 문제를 풀 수 없고, BFS 탐색을 사용해야 한다.

(백준 7576) 토마토 (https://www.acmicpc.net/problem/7576) [설명] ▷ BFS를 활용해 몇일 후에 토마토가 모두 익는지 구하는 문제 ▷ 문제에서 주어진 n, m을 행, 열에 맞춰 선언해주는 것에 주의하자. ▷ 초반 dist[i][j] = -1;로 초기화 해주는 것이 핵심이다. 어차피 최단 거리가 r인 익은 토마토는 모두 값이 갱신되기 때문입니다.

(백준 2146) 다리 만들기 (https://www.acmicpc.net/problem/2146) [설명] ▷ BFS + DFS를 활용하는 문제 ▷ 위의 두 문제를 풀면 해결할 수 있습니다. ▷ DFS를 활용해 섬의 번호를 만들고 BFS를 활용해 섬끼리의 최단거리를 구해 답을 내었습니다.

참고

1. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략
2. https://kks227.blog.me/220769870195