1916번 최소비용 구하기(다익스트라) - ☆

#문제링크 : www.acmicpc.net/problem/1916

<전략>

1. 노드 N개, 간선 M개인 그래프에서 최단거리를 구하는 문제. 그래프에서 최단거리를 구하는 알고리즘 중 가장 성능이 좋다고 알려진 다익스트라를 사용하면 됩니다.

2. 다익스트라는 먼저, 인접행렬 또는 인접리스트로 그래프를 표현한 뒤, dist배열과 check배열을 선언합니다.

3. dist[x] = 시작노드로부터 x번째 노드까지의 최소 거리를 의미하고, check[x]=1은 x노드를 방문했다.를 의미합니다. a[i][j]는 i번째 도시에서 j번째 도시로 가는 비용을 의미합니다.

4. 문제에서 살펴야할 조심해야하는 부분은 도시는 최대 1000개, 버스는 최대 10만개 입니다. 이말은, 중복되는 버스노선이 존재한다는 걸 의미하고, 문제에서 중복된다는 말이 없었기에 수치를 보고 눈치챌 수 있어야 합니다. 사실, 많이 얍삽하다 느꼈던 것도 없지 않아 있네요,,

5. 다익은 dist[start] = 0 으로 초기화해놓고, 시작합니다. 시작점에서 시작점으로의 최단거리는 0이니까요. 먼저, "a[i][j] = i에서 j도시로 가는데 필요한 비용"  이라 하면, 다익스트라 알고리즘을 사용하기 위해서는 a행렬과 dist배열을 발생할 수 있는 비용보다 훨씬 큰 값("버스 비용의 최댓값x노드갯수"보다 큰값)으로 초기화를 해놓아야 합니다. 이 문제에서는 버스의 최대 비용이 99999이고, 최대 노드 갯수가 1000이니, 발생할 수 있는 최대의 비용은 1억미만입니다. 그래서 INF라는 매크로를 1억으로 설정해둡니다. 왜 문제에서 발생할 수 있는 최대비용보다 큰값으로 초기화해야하는지는 밑에서 설명하겠습니다.

6. 다익의 메커니즘은 "방문하지 않은 노드(check=0) 중 가장 작은(최단) dist를 가진 노드를 방문(check=1)하고, 그 노드와 연결된 다른 노드까지의 거리를 계산(dist update)한다." 입니다. 최단거리를 구해야 하기 때문에, dist와 a는 INF로 초기화되어 있어야 합니다. 다익스트라는 "dist[to] (시작~목적지) > dist[from] (목적지 바로 전) + a[from][to] (cost,목적지까지 비용)" 조건문을 통해 최단거리를 갱신합니다. 예를들어,

1 ㅡ 2 ㅡ 3

이런 그래프가 있다고 할때, 시작점은 1이고, 목적지는 3이라 하고, 대충, 모든 간선의 가중치가 1이라 해봅시다.
dist[1~3] = INF, a[1~3][1~3] = INF로 초기화 합니다. 1->3방향으로 가야하므로, a[1][2]=1, a[2][3]=1로 비용을 초기화 해주고 1에서 출발합니다. dist[1]=0로 선언하고 다익스트라 메커니즘으로 들어가면, 아직 check[1]=0이기에, 방문하지 않은 노드중 가장 작은 dist를 가진 노드는 1입니다. 그래서, 1을 방문(check[1]=1)합니다. 그리고 "dist[1~3] > dist[1] + a[1][1~3]" 조건문으로 들어갑니다.

dist[1] > dist[1] + a[1][1]의 경우 -> 제자리 걸음
"시작점~1까지 비용 > 시작점~1까지 비용 + 1~1까지 비용"이라는 뜻으로 "0 > 0 + INF"라 조건문에 성립x

dist[2] > dist[1] + a[1][2]의 경우 -> 경로 탐색
"시작점~2까지 비용 > 시작점~1까지 비용 + 1~2까지 비용"을 뜻합니다. dist[2]는 INF였기에, 오른쪽 항을 보면, dist[1] = 0, a[1][2] = 1(모든 가중치 1이라 가정했습니다 위에서)로 "INF > 0 + 1"이라 할 수 있으므로 조건문에 성립하여 dist[2] = dist[1] + a[1][2] 로 갱신합니다. dist[2] = 0 + 1 = 1

dist[3] > dist[1] + a[1][3]의 경우 -> 없는 경로 탐색
"시작점~3까지 비용 > 시작점~1까지 비용 + 1~3까지 비용"을 뜻합니다. dist[3] = INF(아직 갱신x)이고, dist[1] = 0, a[1][3] = INF(1과 3을 잇는 간선이 존재하지 않으므로, a의 초기값인 INF그대로), 따라서 "INF > 0 + INF"라 성립하지 않고 조건문에 들어가지 않습니다. 

이제, 1은 방문을 했습니다. 방문하지 않은 노드중 dist값이 가장 작은 노드는 2번입니다. 왜냐면, 위의 단계로 dist[2] = 1이 되었고, dist[3] = INF이기 때문입니다. 그래서 이제 2를 방문하고(check[2]=1), 그리고 "dist[1~3] > dist[2] + a[2][1~3]" 조건문으로 들어갑니다.

dist[1] > dist[2] + a[2][1]의 경우 -> 되돌아가는 경로
"시작점~1까지 비용 > 시작점~2까지 비용 + 2~1까지 비용"을 뜻합니다. a[1][2], a[2][3]만 각각 1로 초기화했던 터라, a[2][1]는 INF값을 가집니다. 그래서 "0 > 1 + INF"로 조건이 성립하지 않습니다. 

dist[2] > dist[2] + a[2][2]의 경우 -> 제자리 걸음
"시작점~2까지 비용 > 시작점~2까지 비용 + 2~2까지 비용"을 뜻합니다. a[2][2]=INF이므로, "1 > 1 + INF"라 조건이 성립하지 않습니다.

dist[3] > dist[2] + a[2][3]의 경우 -> 경로 탐색
"시작점~3까지 비용 > 시작점~2까지 비용 + 2~3까지 비용"을 뜻합니다. 3은 아직 갱신한적이 없으므로 dist[3] = INF, a[2][3]=1이므로, "INF > 1 + 1"라 조건이 성립합니다. 따라서 dist[3] = dist[2] + a[2][3] 로 갱신합니다. dist[3] = 1 + 1 = 2

이제, 2는 방문을 했고, 남은건 3뿐입니다. 마찬가지 check[3] = 1하고, "dist[1~3] > dist[3] + a[3][1~3]" 조건문으로 들어갑니다. 위 과정을 보시면 해당 조건문을 굳이 살피지 않아도 조건문이 성립하는 구간이 없다는 것을 알아채셨을 겁니다. 이렇게 다익스트라 메커니즘이 끝나게 됩니다.

7. 이런 이유로 처음에 a행렬을 INF값으로 초기화시켜주는 겁니다. 되돌아가는 경우, 간선이 없는 경로 탐색, 제자리 걸음하는 경우에 조건문을 반드시 false하기 위해..! 그리고 dist를 INF로 초기화하는 이유는 최단 경로로 갱신하기 위해..!

8. tmp = INF로 해도 되지만, 그러면 반드시 a행렬을 인덱스 0부터 끝까지 INF로 초기화해야 합니다. 지금 작성된 코드는 1부터 끝까지 INF로 되어있어서, a[0][j]나 a[i][0] 꼴의 값은 모두 0입니다. 이상태에서 그냥 tmp = INF로 해버리면 경우에 따라 dist배열이 모두 0으로 초기화될 수 있습니다. 주어진 길을 모두 지나가더라도 거쳐가지 않은 길들이 존재하는 경우에 그렇습니다.

예를 들어, 1->2, 1->3, 3->4, 5->3와 같은 길(가중치 모두 1)이 있다고 할 때, 시작점은 1, 도착점은 4라고 해봅니다. 그러면 dist[1] = 0 , dist[2] = 1, dist[3] = 1, dist[4] = 2, dist[5] = INF가 됩니다. dist[5] = INF인 이유는, 1에서 5로 갈 수 있는 길이 없기 때문입니다. 이 경우, 1~4까지는 모두 방문해서 check값이 1이지만 5는 방문을 못했기에 check값이 0입니다. 이렇게 되면, int x= 0;으로 초기화 한 이후에, "check[j] == 0 && tmp > dist[j]"라는 조건문을 통과하지 못합니다. 결국 x = 0으로 남고, check[0] = 1이 된 후, "dist[j] > dist[0] + a[0][j]"가 되기 때문에 dist[0] = 0, a[0][j] = 0으로 항상 조건문에 성립하여 결국 모든 dist[j]값이 0으로 바뀌어버립니다. 그래서, a행렬의 인덱스를 0부터로 바꾸어주고 INF로 초기화하면 됩니다.

Code