🛣️ Shortest Path in an Unweighted Graph

intro

🛣️ 그래프에서 최단거리를 구하는 알고리즘은 여러가지가 있다. 다익스트라, 플로이드-워셜, 벨만-포드와 같은 유명한 최단거리 TOP 3 알고리즘이 존재하는데, 간선의 가중치가 전혀 없는, 주어진 일반적인 그래프에서의 최단 거리를 구하는 방법은 BFS가 best. 이번 포스팅을 통해 주어진 그래프에서 BFS를 사용해 최단거리 구하기와 최단거리 내용 출력까지 알아본다.

DFS는 안되고 BFS는 가능한 이유?

🛣️ 그래프 순회의 대표적인 2가지 방법으로는 DFS, BFS가 있다. 그러나 shortest path in an unweighted graph를 찾기 위해서는 DFS보다는 BFS 방식을 적극 권장. 접근 방식에 차이가 있기 때문이다.

 

: BFS의 경우 level-wise exploration 형태로 그래프 레벨별로 탐색을 시작한다. 즉, 시작노드로부터 d 거리에 있는 모든 노드는 (d+1) 거리에 있는 그 어떤 노드를 탐색하기에 앞서서 모두 탐색되기 때문. 즉, BFS가 처음으로 한 노드에 도달할 때, 해당 노드까지의 도달 shortest path를 구한 셈. 추가로 BFS는 queue 자료구조를 사용하므로, 먼저 방문한 노드부터 처리하기 때문에 해당 노드까지 도달하는 path는 shortest하다는 점도 guarantee됨.

 

: 반면에 DFS의 경우 depth-wise exploration 방식으로 먼저 딥하게 나중의 traversal process에서 발견되는 shorter path가 있을 수 있다.

BFS의 depth가 곧 최단거리다

🛣️ node A의 BFS의 depth는 곧 starting node부터 node A까지의 edges(간선) 개수이다. (아래 그림 참조)

: 위 그림을 보면 node D의 depth는 starting node A부터 node D까지의 간선의 개수로, 2임을 알 수 있다. (source node를 level 0 가정)

 

🛣️ 그렇다면 해당 node D의 최단거리(starting node A부터 시작)는 2임을 어떻게 증명할 수 있을까? 아래 명제를 먼저 증명해보자

 

" 간선 (U,V)를 통해서 정점 V를 처음 발견해 queue에 넣었다고 가정. 이 때 시작점(source node S)에서 정점 V까지의 최단거리 dist(S,V)는 시작점에서 정점 U까지의 최단거리 dist(S,U) + 1이다" → "dist(S,V) = dist(S,U) + 1"

 

① dist(S,V) > dist(S,U) + 1

: 자명하다. S에서 U까지의 경로에서 간선 (U,V)로 1개를 더 붙이면 dist(S,V)가 dist(S,U) + 1이 될 수 있기 때문이다.

 

② dist(S,V) < dist(S,U) + 1

: V까지의 거리가 U 까지의 거리 + 1보다 짧다고 가정. 그렇다면 짧다고 가정한 해당 경로 상에서 V 노드 바로 이전의 정점은 당연히 U까지의 거리보다 작아야 한다. V 노드 바로 이전의 정점을 P라고 한다면, dist(S,P) = dist(S,V) - 1이므로, 아래와 같이 부등식을 나타낼 수 있다.

 

dist(S,V) < dist(S,U) + 1 & dist(S,P) = dist(S,V) - 1 ↔ dist(S,P) < dist(S,U) + 1 - 1 = dist(S,U)

 

따라서, dist(S,P) < dist(S,U)와 같은 식이 완성된다. 즉 해당 식을 통해 우리는 BFS 탐색 알고리즘 상 노드 P를 노드 U보다 우선 방문했음을 알 수 있다. 이 때 노드 P는 노드 V 바로 이전의 정점으로, 종합하면 노드 P를 방문 후 노드 V를 방문하게 된다. 그런데 노드 U보다 노드 P를 우선 방문했음을 도출했으므로 (1) 노드 U는 노드 V와 같은 레벨(depth)에 있거나, (2) 노드 V 방문 후 노드 U를 방문하는 두 케이스로 나눌 수 있다. 하지만 간선 (U,V)를 통해 위 (1)과 (2)는 모두 모순임을 알 수 있으므로 귀류법에 의해 ②도 False.

 

→ 따라서, 간선 (U,V)가 존재한다면 dist(S,V)는 dist(S,U) + 1임을 알 수 있다. (dist(X,Y) = 정점 X에서 정점 Y까지의 최단거리)

 

🛣️ 따라서 예를 들어 노드 A에서 노드 D까지의 최단거리를 구하고 싶다면 노드 A에서 시작해 BFS를 탐색해 노드 D까지의 depth가 최단거리(노드 A의 depth 0 가정)

Shortest Path BFS code

🛣️ 아이디어:

(1) 원래의 BFS 코드에서 각 노드별(1번 노드 ~ N번 보드) depth가 저장된 1차원 list 만들기(-1로 처음에 모두 초기화)

(2) 시작 노드 depth 0 설정

(3) queue 돌면서 popleft()로 뺀 노드의 인접 노드 for문 중 특정 노드 첫 방문 시, 원래 노드 depth에 1을 더한 결과를 depth에 저장

(4) 최종적으로 구한 depths list에서 도착 노드에서의 depth 출력하면 시작점에서 도착점까지의 최단 거리 출력

Shortest Path 내용 & 개수 구하기

① Shortest Path 최단거리 노드 번호 구하기

: 단순히 최단거리가 몇인지를 물어보는게 아니라, 최단거리의 내용(노드 번호)을 물어보는 유형도 존재. path list를 만든 뒤(A), A[3]은 3번 node를 자식 node로 하는 부모 node 번호를 저장. 예를 들어 아래와 같은 그래프를 BFS로 탐색한다면,

ex) 1번 노드의 부모 노드 번호는 2이므로 path[1] = 2, 2번 노드의 부모 번호 노드는 3이므로 path[2] = 3 ~ 이렇게 진행된다. 시작 node의 부모 번호 node는 0으로 설정(path[5] = 0). 따라서 도착점에서의 node부터 역추적으로 path list를 진행해 path[5] = 0 결론이 될 때까지 역추적 경로를 출력한다.

 

② Shortest Path 최단거리의 갯수를 추가로 구할 수 있다. 

ex) 1에서 6까지 가는 최단거리의 갯수를 구해보자. 이 때 parent node를 v라 하면 뻗을 수 있는 경로의 개수는 v-1, v+1, 2*v 세 가짓수.

(1) 주어진 숫자 범위 아닌 child node 제외(노란색 X)

 

(2) ex) 현재 node에서 v-1, v+1, 2*v로 뻗었을 때(BFS 탐색)

① child node가 목표 node가 아닌 경우

[1] child node를 방문하지 않은 새로운 node (위 그림 보라색) : depths update, visited True 설정, queue에 넣기

 

[2] child node를 이미 방문한 node(ex 위의 그림의 경우 depth 1에서 2로 뻗을 때 node number 2) (위 그림 초록색) : 동일한 number의 node는 동일 depth에 있을 때만 이후 탐색 가능하고, 이미 이전 depth에 존재한다면 pass

→ 따라서 depths[child] == depths[v] + 1일 경우만 depths update, queue에 넣기

 

② child node가 목표 node인 경우

[1] 첫 목표 node 도달이라면(found == False) (위 그림 빨간색): depths update, visited True 설정, queue에 넣기, found = True, found_depth 설정, cnt(정답변수) += 1

 

[2] 이미 도달한 적이 있다면 (위 그림 노란색): found_depth == depths[v] + 1일 경우만 cnt += 1

 

+ return 종료 코드 넣기 +

 

① child node가 목표 node가 아닌 경우

[1] child node를 방문하지 않은 새로운 node인 경우(위 그림 보라색)

: if found 답 찾았다면 → found_depth보다 현재 depth[child]가 더 크다면, return 종료(그 다음 depth로 진행된 것이므로)

 

[2] child node를 이미 방문한 node인 경우(위 그림 초록색)

: 동일한 number의 node가 동일 depth에 있을 경우 → if found 답 찾았다면 → found_depth보다 현재 depth[child]가 더 크다면, return 종료(그 다음 depth로 진행된 것이므로)

 

② child node가 목표 node인 경우

[1] 처음으로 도달(위 그림 빨간색)

: return x

 

[2] 이미 도달한 적 있는 경우(위 그림 노란색)

: 이미 찾은 found_depth와 현재 depth(depths[v]+1)와 서로 같지 않다면, return 종료

 

※ 최단경로 갯수 핵심은, found bool flag 변수를 만든 뒤,

처음으로 도달하지 않은 경우(found==True)일 때 처음으로 도달했을 때의 node depth(found_depth)와 현재 depth를 비교. 즉 depth를 비교하면서 최단경로 갯수를 update하면 된다. 그리고 현재 depth가 found_depth를 넘어섰으면 return 종료 ※

Shortest Path Exercises

examples

★ <BOJ S2 16953 A → B> ★

: 정수 A를 B로 바꾸기 위해 필요한 연산 횟수의 최솟값 구하기. BFS 최단거리 유형임을 알아차리는 게 중요. 2를 곱한 경우와 1을 붙인 두 갈래를 BFS 방식으로 depth 별로 뻗어 나가면서 최소 간선의 횟수(최소 depth)로 원하는 결과가 나오면 바로 depth를 최단거리로 출력

 

★ <BOJ S2 1644 촌수계산> ★

: 가족의 촌수는 BFS의 depth임을 인지하면 바로 풀림

 

★ <BOJ S1 1697 숨바꼭질> ★

: 위 16953 문제와 동일. X-1, X+1, 2*X 세 갈래로 간선 뻗어나가기

 

★ <BOJ S1 7562 나이트의 이동> ★

: 역시 동일. 나이트의 최소 이동 횟수 BFS의 depth로 구하기

 

★ <BOJ S1 5014 스타트링크> ★

: 역시 동일. 단, 1차원 배열에서의 BFS depth 구하기

 

★ <BOJ S1 2178 미로 탐색> ★

: 역시 동일. 시작점과 도착점이 주어진 상태에서, 시작점에서 도착점까지 갈 수 있는 최단거리 구하기

 

★ <BOJ S1 16948 데스 나이트> ★

: 역시 동일. 단, 움직이는 방향이 무려 6방향인 점만 숙지하면 끝

 

★ <BOJ S1 14940 쉬운 최단거리> ★

: 동일. 다만 그래프에 도달 못하는 지점이 있는 조건 추가

 

★ <BOJ S2 17086 아기 상어2> ★

: 단순한 brute-force로 풀리는 문제. 하지만 BFS 관점으로 푼다면, 여러 상어와의 안전거리 최솟값을 구해야 하므로, 아기 상어 각각 시작점으로 depth update. 최솟값이므로 기존 depth보다 작을 때만 update. depth 관점 아이디어 생각해야 할 문제

 

★ <BOJ G5 7576 토마토> ★

: 시작점이 여러 개에서 시작하는 BFS 최단거리 교과서 유형

 

★ <BOJ G5 7569 토마토> ★

: 높이까지 존재하는, 7576의 3차원 버전. 방향벡터가 dx, dy, dz 세 개 존재. 방향은 6가지 주의

 

★ <BOJ G5 1240 노드 사이의 거리> ★

: 최단거리 변형 문제. 각 간선마다 거리가 존재해서, BFS를 돌리면서 업데이트 되는 거리를 queue에 같이 돌리며 depth update.

 

★ <BOJ G5 13539 숨바꼭질 3> ★

: BFS를 진행하되, 우선순위가 존재하는 간선이 있는 유형. 따라서 우선순위가 있는 간선 방향 진행을 먼저 queue에 popleft()하고 append()

 

★ <BOJ G4 13913 숨바꼭질 4> ★

: 최단거리 내용까지 역추적하는 문제. 

 

★ <BOJ G5 16928 뱀과 사다리 게임> ★

: 노드에서 노드로 단숨에 이동하는 경로를 추가로 고려

 

★ <BOJ G4 9019 DSLR> ★

: BFS 최단거리 유형임을 알고, queue에 노드번호 + 해당노드내용 이렇게 2개를 넣는다는 점만 기억

 

★<BOJ G4 1963 소수경로> ★  

: BFS임을 알고 소수 성질만 추가된 문제

 

★<BOJ G4 12851 숨바꼭질 2> ★

: 최단거리의 가짓수를 구하는 문제(depth 활용)

---

geeksforgeeks

BFS 최단거리 depth + 1 증명