[최소 간선 이동 횟수] - BFS의 부가 효과

[jusung-c]

BFS의 부가 효과

그래프가 주어지고 시작점이 주어졌을 때 그 시작점에서 갈 수 있는 정점들을 찾는 것이 그래프 탐색이었다.

그런데 이 시작점에서 원하는 지점까지 몇번으 ㅣ이동이 필요한지에 대한 답은 할 수 없다. BFS, DFS를 떠나서 그래프 탐색만으로는 알 수 없다.

하지만 BFS의 부가 효과를 잘 이용하면 시작점에서 어떤 정점까지 갈 수 있느냐 뿐만 아니라 가는데 필요한 최소 이동 간선 횟수까지 알 수 있다.

이것은 DFS가 아닌 BFS만 가지는 성질이다.

BFS를 진행할 때 거리를 계산할 dist[] 배열을 만들어준다. dist[i]가 의미하는 것은 주어진 시작점에서 정점 i까지 갈 때 필요한 최소 간선 횟수를 뜻한다. 만약 이동이 불가하다면 -1 값을 가지도록 한다.

당연하게도 dist[S] 시작점의 값은 0이고, dist[X] 값을 알고 있을 때 X 정점에서 Y 정점으로 하나의 간선으로 이동했을 때 dist[Y]의 값은 dist[X] + 1이 될 것이다. 이 성질을 이용해 탐색을 진행하면서 최소 간선 개수를 구할 수 있는 것이다.

왜 BFS(너비 우선 탐색)이라고 이름을 붙였을까를 생각해보자
물에 돌을 던졌을 때 돌을 던진 위치를 기준으로 파동이 생길 것이다.

첫 번째 파동부터 탐색을 진행한다. 첫 번째 파동에 위치한 정점들은 dist값이 1일 것이다.

그 첫 번째 파동에 위치한 정점들에서 다시 파동이 진행하면 dist값이 2가 된다.
즉, 시작점에서부터 너비가 좁은, 즉 거리가 가까운 지점부터 탐색을 진행하기 때문에 너비 우선 탐색이라고 이름을 지은 것이다.

핵심 키워드

최소 "이동" 횟수와 관련된 것이기 때문에 가중치에 대한 개념이 없는 문제에서만 생기는 부가효과이다!

만약 "A -> B로 이동하는데 드는 비용"처럼 가중치 개념이 나오면 이 부가효과는 의미가 없어진다.