[BOJ] 단계별로 풀어보기 - 최단 경로

 

 

 

 

 

https://www.acmicpc.net/step/26

최단 경로 단계

---

코딩 구현 속도와 베이스를 다지기 위해 백준 단계를 하나씩 다 풀어보는 중 ...

 

1. 1753 최단경로: https://www.acmicpc.net/problem/1753

Dijkstra

 

 

 

 

 

2. 1504 특정한 최단 경로: https://www.acmicpc.net/problem/1504

주어진 두 정점을 반드시 거쳐야한다 (제약조건) + Dijkstra

 

Dist(u, v) = u ~ v까지 최단 거리 라고 하면,

$Dist(1, v_1)+Dist(v_1,v_2)+Dist(v_2,N)$ 또는,

$Dist(1, v_2)+Dist(v_2,v_1)+Dist(v_1,N)$ 이 답이 된다는 사실을 관찰할 수 있다.

 

따라서 $v_1$과 $v_2$를 시작점으로 하여 Dijkstra를 총 2번 돌려야 한다.

위 수식을 약간 변경하여,

$Dist(v_1, 1)+Dist(v_1,v_2)+Dist(v_2,N)$ 

$Dist(v_2, 2)+Dist(v_2,v_1)+Dist(v_1,N)$

이렇게 얻은 결과값을 계산하여 최솟값을 답으로 하면 AC.

 

 

 

3. 9370 미확인 도착지: https://www.acmicpc.net/problem/9370

특정 선분을 반드시 거쳐야한다 (제약조건) + Dijkstra

 

위에 문제가 특정한 정점을 지나는 Dijkstra를 구현하는 문제였다면, 

이 문제는 특정 선분을 지나는 Dijkstra를 구현하는 문제이다.

 

Dijkstra에서 최단 경로를 구할 때,

g-h 선분을 지나는 최단경로들은 따로 chk배열을 이용하여 구분해줌으로써 문제를 해결하였다.

방법은 아래와 같다.

 

1. 최단경로가 갱신될 때, cur와 next가 주어진 선분의 양 끝점이라면, next 정점을 check 해준다.

if ((cur == g && next == h) || (cur == h && next == g)) chk[next] = true; 

여기서 주의할 점은 next 정점의 check 배열만 갱신해준다는 것이다. 

cur도 check 배열을 갱신해주면, cur->next 선분을 지나지 않고 cur만 지나는 정점들도 갱신되어 오답이 발생한다.

 

2. 최단경로가 갱신될 때, cur가 chek 되어있으면, next 정점을 check 해준다.

if (chk[cur] == ture && cur.first + next.first == cost[next]) chk[next] = true;

.first 는 간선의 가중치에 해당하는 부분이고 cost 배열은 각 정점까지의 최단거리가 저장된다.

cur 정점까지 가는 최단경로가 g-h 선분을 지난다고 하면,

cur->next 선분을 통해 next까지 가는 최단경로도 당연히 g-h 선분을 지난다는 걸 알 수 있다.

 

이 문제에서 크게 주의해야할 상황은 두가지가 있다.

1. 동일한 최단경로가 여러개이고, 이 중 g-h를 지나는 경로가 존재할 시

 보통 dijkstra에서 최단 경로를 갱신할 때,

if (cur.first + next.first >= cost[next]) continue;

이런 식으로 거리가 갱신되지 않으면 추가작업(ex. queue push)들을 무시해버린다.

만약 이렇게 코드를 작성하면, 1->3까지 가는 최단 경로가 1->2->3 이렇게 갱신되기 때문에,

1->4 간선이 무시되어 잘못된 해답을 낼 수 있다.

 

2. 최단 경로인 줄 알았던 경로가 마지막에 최단 경로가 아니라고 판별날 시

작성자는 이 부분에서 오답을 뱉어냈었다..

새로 갱신되는 최단 경로가 g-h를 지나지 않을 때 chk 배열을 false로 바꿔주는 코드를 넣지 않아 오답이 발생했었다.

위의 경우에는 1->2->3->4 처음에 이렇게 dijkstra가 돌면서 chk[4] = true 로 갱신된다.

하지만 후에 1->5->4 경로를 지날 때, 이 경로가 최단경로로 갱신되면서 chk[4] = false로 바꿔줘야한다.

 

첨부한 코드는 priority_queue 라이브러리를 간편하게 이용하기 위해 가중치를 모두 음수로 바꿔주어 부등호 방향이 반대로 바뀐다.

 

 

4. 11657 타임머신: https://www.acmicpc.net/problem/11657

음수인 가중치도 들어오기 때문에 벨만-포드 알고리즘을 이용

 

 

 

5. 11404 플로이드: https://www.acmicpc.net/problem/11404

각 정점 사이의 최단거리를 모두 구하는 문제

n 제한이 작기 때문에 플로이드-와샬 알고리즘을 이용

 

 

 

6. 10217 KCM Travel: https://www.acmicpc.net/problem/10217

최단경로보다는 DP가 핵심인 문제 (굳이 Dijkstra를 쓰지 않아도 된다)

 

D[u][m]: 1~u까지 m 이하의 비용을 사용할 때의 최소 소요시간

이렇게 DP table를 정의 내리고 구하면 된다.

 

기존 Dijkstra에서 최단거리를 갱신하는 배열은 보통 cost[] 이렇게 1차원 배열로, 각 정점까지의 최단거리가 저장되었다.

이 문제에선 이 cost 배열을 2차원으로 늘려서 D[u][m] 이렇게 바꾸면 된다.

앞에서 굳이 Dijkstra를 쓰지 않아도 된다고 한 이유는 m 이하의 비용을 맞추는 경로가 최악의 경로일 시 어차피 모든 경로를 다 돌아봐야 하기 때문이다.

따라서 작성자는 우선순위 큐가 아닌, 큐를 이용하여 코드를 작성하였다.

 

시간제한은 10초로 넉넉하기 때문에 컷팅을 빡세게 하지 않아도 통과할 수 있는 문제다.

굳이 실행시간을 줄이겠다면, 

for (int j = newCost; j <= M; ++j){
	if (dist[i.p][j] > newDist) dist[i.p][j] = newDist;
	else break;
}

이런식으로 컷팅을 해줄 수 있다.

만약 m만큼의 비용을 이용하여 구한 최소 소요시간이 

m+1, m+2, m+3, ... 이렇게 기존에 구했던 그 이상의 비용을 사용했을 때마다 적게 걸릴 시

이를 모두 한꺼번에 갱신해준다.

그리고 큐에서 하나씩 값을 꺼내올 때, 위에 해당하는 것들은 걸러주면 실행시간을 줄일 수 있다.

 

 

 

7. 1956 운동: https://www.acmicpc.net/problem/1956

1 -> a -> b -> c -> ... -> 1 이렇게 cycle을 이루는 경로 중에서 최단경로를 구하는 문제

V 제한이 400으로 매우 작기 때문에 플로이드-와샬 알고리즘 이용.

 

$ans = Min_{a,b \in V, a\neq b}(Dist[a][b]+Dist[b][a])$