0-1 bfs 알고리즘 : 가중치가 0과 1만 있을 때 최단거리는 어떻게 구할까요?

 가중치가 0과 1만 있는 그래프에서 최단 거리는 어떻게 구할까요? 얼핏 들어서는 그냥 다익스트라를 잘 이용하면 될 거 같습니다. 그런데, deque나 Queue 구조만을 이용해서 코딩을 할 수 있습니다. 이게 어떻게 가능할까요?

 

 

---

 먼저, 가중치는 0과 1만 있어요.

 

 

 그리고 알고리즘 1은 위와 같습니다. 해석해 보면 그렇게 복잡하지 않아요. 시작 지점을 s라 합시다. 처음에는 s까지 최단 거리가 0이다. 라는 정보를 dq에 넣을 겁니다. 그리고, 자료 구조 dq의 앞 부분에서만 정보를 뺍니다. 이 정보는 to까지 min_dist가 cost다. 입니다. to와 인접한 지점을 a라 합시다. 이 때, to로부터 a까지 거리가 0이라면, a까지 거리에 대한 정보를 dq의 앞에 넣고, 아니라면 dq의 뒤에 넣습니다. 이렇게 해도 문제 없을까요? 우리가 증명해야 할 명제는 아래와 같습니다.

 

 일단, 처음에 start부터 어떠한 노드까지 최단 거리가 t라는 정보를 저장하고 있는 자료구조는, 비어 있는 상태입니다. 그러면 보라색으로 칠한 조건을 만족합니다. 다음에, start에서부터 start까지 거리가 0인 정보를 넣을 거니, 1개의 최단 거리를 가질 겁니다.

 

 그러면 보라색 조건이 성립합니다. 기저가 성립하는 것입니다. 이제, P(n)이 성립할 때, P(n+1)이 성립하는지 여부를 봅시다. 먼저, 1개의 최단 거리만을 가지는 경우를 생각해 봅시다.

 

 

 알고리즘 1의 7번째 줄을 보면, deque에서 맨 앞의 원소를 빼라고 되어 있습니다. 이 때 dist 값이 d라고 해 봅시다. 즉 start에서 to까지 가는 최단 거리가 d다. 라는 정보가 deque의 맨 앞에 있다고 생각해 봅시다.

 

 

 

 그러면, to까지 가는 최단 거리가 d라는 상태일 겁니다. 그러면 to에서 다른 목적지 a까지 가는데, 걸리는 시간이 0 아니면 1일 겁니다. 만약에 to에서 a까지 거리가 0이면서 a를 방문하지 않았다면 어떻게 하라고 되어 있나요?

 

 

 앞에다 넣으라고 되어 있습니다. 이 때, 앞에 들어가는 정보는 시작점에서 a까지 가는데 최단 거리는 d다. 라는 것입니다. 만약에 to에서 a까지 가는데 거리가 1이면 어떻게 될까요? a는 방문하지 않았다고 하고요. 

 

 

 그러면 시작 점에서, a까지 가는 데 최단 거리는 d+1이다. 라는 정보가 생성이 될 거에요. 가중치에 1이 더해졌다. 그러면, 알고리즘 1에 따르면 back에 넣으라고 되어 있어요.

 

 집합 내에 있는 최단거리가 d, d+1만 있는 데다가 sorting 까지 되어 있어요. 초록색 조건을 만족하네요. 따라서 P(n)이 성립했을 때, 알고리즘 1을 따르면 P(n+1) 또한 성립한다는 것을 알 수 있어요. 즉, 1개가 있는 상태에서 갈 수 있는 state는 1개만 있거나, 2개만 있거나. 둘 중 하나입니다. 그런데 2개만 있을 때 sorting이 되어 있는 상태입니다. 이것을 조금 더 확장을 시켜 봅시다.

 

 

---

 

 그러면, 이런 경우도 생각해 볼 수 있어요.

 

 자료 구조에 저장이 되어 있는 최단 거리 정보가 d, d+1만 있다고 생각해 봅시다. 즉, P(n)이 초록색 조건을 만족하는 경우입니다. 알고리즘 1에 따르면, 이 때에도 dq.front()를 뺀다고 되어 있습니다.

 

 

 즉, 노란 색으로 칠한 부분입니다. 이것을 빼 봅시다.

 

 

 그러면 이 상태입니다. start에서 to까지의 min_dist가 d다. 라는 정보를 빼 왔다고 생각해 봅시다. 마침 to부터 a까지 거리가 0이였다고 해 봅시다. 그러면 d + 0 = d이니까 a까지 min_dist는 d입니다. 더해진 가중치가 0이므로, [1]에 따르면, 앞쪽에 넣는다고 되어 있습니다.

 

 

 정렬된 상태인가요? 네. 심지어 자료구조에 거리에 대한 정보가 d, d+1만 존재합니다.

 

 

 만약에, to부터 a까지 거리가 1이였다고 해 봅시다. 가중치가 1이였기 때문에, 이 때에는 deque의 뒤에 넣어야 합니다. a까지 최단 거리가 d+1인 정보를, 알고리즘 1에 따라서, 뒤에 넣었다고 생각해 봅시다.

 

 

 그러면 어떻게 되나요? 하늘색 부분은 d인 것들, 군청색 부분은 d+1인 것. 그리고 보라색은 d+1인 것입니다. 초록색 조건이 성립합니다. 따라서, 위 명제가 성립합니다. 기저 조건이 증명되었고, P(n)이 T일 때 P(n+1)이 T임을 증명함으로서, 성립한 것을 보인 셈입니다.

 

 

---

 그러면, dq의 맨 앞에서 빠진 정보인, s에서 to까지의 최단 거리는 d다. 라는 정보가 답이 될 수 있을까요? 그것도 최초로 deque에서 to에 대한 정보가 빠진 정보가요. 슈도코드로 작성한 BFS_01 함수의 8번째 줄에 따르면, to가 이전에 dq에서 빠졌다면 continue를 해 버립니다.

 

 

 이는, dq의 front에 있는 가중치는 제일 작은 가중치이기 때문입니다. 그리고, 이에 대한 정보가 start에서 to까지의 거리가 d이다. 라는 정보입니다. 이 정보가 빠지고 visit[to] = 1이 되었습니다.

 

 

 현재 deque에 있는 것이 to, A(1), ... , A(n)까지의 dist라고 해 봅시다. deque의 맨 앞에 있는 것이 to까지 최단 거리가 d다. 라는 정보라면 A(1), ... , A(n)까지의 최단 거리는 d보다 크거나 같을 겁니다. 그러면 deque의 A(1), ... , A(n) 중에서 하나를 경유해서 to까지 간 최단거리가 d보다 작아지려면 어떻게 되어야 할까요? 빨간색으로 칠한, 그러니까 A(1)부터 to까지, A(2)부터 to까지, ... , A(n)부터 to까지의 최단 거리가 0보다 작아져야 합니다.

 

 그럴려면 음수 가중치가 있어야 하는데, 그렇지 않아요. 단지 0과 1만 있습니다. 0과 1은 음의 가중치가 아닙니다. 따라서, to까지의 최단 거리가 아직 결정되지 않은 상태에서, deque에서 빠진 정보가 to까지의 min_dist가 d라는 정보일 때, 그 다음에, to까지의 거리에 대한 정보가 빠졌을 때 무시해도 됩니다. 0-1 BFS 정도는, 이런 것이 있구나 정도로만 알아두셔도 무난한 거 같아요.