BOJ 13907 세금 - 벨만 포드, 다익스트라 공부하고 다시 풀어보기...

여러 도시들과 그 도시들을 잇는 도로와 통행료가 주어진다. 그리고 출발점 도시A와 목적지 도시B가 주어지는데 이 때, A에서 B로 가는 길의 통행료의 합이 가장 작은 경로를 구해야 한다. 정확히는 최소의 통행료를 구해야 하는데, 이럴 경우 다익스트라를 이용하면 쉽지만, 이 문제에서는 매 단계별로 모든 도로의 통행료가 입력에 각 단계별로 주어진 만큼 인상된다. 이 때, 각 단계별 A에서 B로 가는데 드는 통행료의 최소값을 구하는 문제이다.

매 단계별로 다익스트라를 다 돌려보는 것이 가장 쉬워보이지만 그럴 경우 TLE를 받게 된다. 어떻게 해야할까? 여러 방법이 있겠지만 난 다익스트라를 이용해서 풀어봤다.

이 문제에서 핵심은 A에서 B까지 몇 개의 길을 거쳐 갔는지이다. 각 단계에서 세금을 인상할 때, 모든 도로의 통행료가 인상되기 때문에 A에서 B까지 거쳐간 길이 많을 수록 전체 통행료가 많이 올라가게 된다. 즉, 몇 단계에 걸친 세금 인상마다 통행료가 최소인 경로가 달라질 수 있는 것이다. 

좀 더 생각해보면 세금이 인상됨에 따라 현재 최소인 경로보다 거쳐간 길의 개수가 적은 경로들이 최소가 될 가능성이 있는 경로들이다. 거쳐간 길이 많은 경로들은 그럴 가능성이 없다. 

그런데 여기서 더 이상 나아가진 못하고 일단은 다익스트라를 이용하되, 일반적인 다익스트라 알고리즘에서는 한 정점에서 다른 정점까지의 최단 거리를 구했다면, 이 문제를 풀 때는 한 정점에서 다른 정점까지 x개의 길을 거쳐가는 최단 거리를 구하는 식으로 생각해 봤다.

d[node] = src에서 node까지의 최단 거리... 였다면,

d[node][x] = src에서 node까지 x개의 길을 거쳐서 가는 최단 거리로 놓는다.

d[node][x] > d[node][x-1] + cost 이면 d[node][x]를 업데이트 해주는 식으로 다익스트라를 구현한다. 근데 도시의 개수가 1000개 그 도시들을 잇는 길의 개수가 30만개라서 처음에 

d[1001][300000]로 잡았다가 메모리 초과가 났는데, 생각해보니 저렇게 잡을 필요가 없다.

d[1001][1000]이면 된다. 왜냐하면 최단 경로는 최대 node-1개로 이루어질 수밖에 없기 때문이다. node-1개의 경로보다 많은 경로를 거치면 한 점을 두 번 이상 방문하게 되므로 불필요한 방문을 한 것이고 최단 경로가 될 수 없으므로 고려할 필요가 없다.

그리고 저렇게 구현하고도 또 틀렸는데, 내가 방문한 경로가 node-1을 넘어가는 경우도 그냥 나둬서 그런 것이었다. 중간에 node-1개를 방문했으면 그 node까지의 최단 거리는 더 이상 구할 필요가 없다.

그래서 결국 AC를 받았는데, 맞은 사람 목록에서 다른 사람들의 코드와 시간이 10배 정도 차이가 난다. Baekjoon Online judge게시판에 이 문제에 대한 풀이(서강대 대회 문제였다.)가 올라와 있다고 하니 보고 공부하고 다시 풀어봐야 겠다.

풀이를 봤는데 일단 접근은 비슷한 것 같은데 구현이 다익스트라가 아닌 벨만포드 비슷한 방식으로 한 것인데... 벨만포드를 까먹어서..(아..복습ㅠ) 왜 다익스트라보다 10배 정도나 빠른건지...제대로 이해하지는 못하고 다른 분들 코드도 보다가.. 다익스트라를 쓰신 것 같은데도 불구하고(게다가 자바로 구현하셨는데도...) 속도가 매우 빠른 분이 계셔서, 그 코드를 이해는 못했지만 다익스트라도 시간을 단축시킬 수 있다는 희망을 가지고 나도 내 코드에서 좀 더 시간을 단축시킬 방법을 고민해 봤다.

생각해보면 어떤 점 V까지의 최단 거리를 구할 때, V까지 n개의 길을 거쳐서 가는 최단 거리를 구했다고 치자. 근데 매번 세금이 오를 때마다 통행료가 길의 개수만큼 인상되기 때문에 V까지 같은 최단거리라면 길의 개수가 더 많은 경우는 볼 필요가 없다.

다익스트라 알고리즘에서 난 priority queue를 사용했기 때문에 최대한 pq에 들어가는 간선을 줄이면 시간과 메모리를 단축시킬 수 있을 것이다. 

V까지의 n개의 경로를 거쳐 간 최단 거리가 V까지의 n-1개 이하의 경로를 거쳐 간 최단 거리보다 같거나 혹은 크다면 더이상 V까지의 n개의 경로를 거쳐 간 경우와 그 경우에서 파생되는 경우는 볼 필요가 없어서 큐에 넣지 않았다. n-1개 이하의 경로를 거쳐간 최단 거리와 거기서 파생된 경우만 보면된다.

근데 n-1개 이하의 경로를 거쳐간 경우를 보기 위해서 for문을 n번 돌려주기 때문에(break을 넣긴 했지만) 오래 걸리지 않을까 걱정도 했지만... 제출해보니 시간이 무려 20배정도 단축됐다(메모리는 3배정도)... 내가 이 다익스트라에서 2차원 배열을 쓰는 경우의 시간 복잡도를 모르겠는 것도 있고 지금 다익스트라, 벨만포드등을 다시 공부해봐야 할 것 같아서 왜 이런 결과가 나왔는지 정확히 내 알고리즘의 개선이 얼마나 된건지 아니면 테스트 케이스가 약해서 그런건지.. 잘 모르겠다.  풀이는 dp로 이해하면 될 것이다.

일단 공부를 더 해보고 이 문제는 다시 풀어봐야 겠다.
-------------------------------------------------------------------------------------
풀이를 봤더니 dp였다.
d[n][r] = n번도시 까지 r개의 길을 거쳐 갈 수 있는 최단 거리
d[n][r] = min(d[pre][r-1], pre는 n번도시와 연결된 도시들) 혹은
d[here][r]을 이용해서 d[there][r+1]을 구할 수 있을 것이다.
d[src][0]=0으로 두고 배열을 채워 나가면 최단 거리가 구해질 것이다.

이렇게 dp로 구현하면서 어떻게 시간을 단축시킬까 고민하다가
위에서 이용한 원리를 또 사용해봤다.
d[n][r]배열을 구하는 곳에는 적용 못할 것 같아서 마지막에 세금을 올리는 단계별로 최소값을 구해서 출력하는 과정에서 적용했는데, 세금을 올릴 수록, 답이 되는 최소경로는 반드시 지나는 길의 개수가 같거나 작아질 수 밖에 없다. 세금이 지나는 길의 개수에 비례해서 늘어나기 때문에 세금을 부과하는 단계가 높아질수록 최소경로는 이전과 지나는 길의 개수가 같거나 작을 수밖에 없는 것이다.
이 사실을 이용해서 최소 경로를 구할 때, 지나는 길의 개수를 저장해두고, 최소 경로를 구할 때마다 이전 최소 경로의 길의 개수이하인 경우만 보는 식으로 구현했다.  이전 최소 경로의 길의 개수보다 큰 경우는 절대 최소 경로가 될 수 없다.

그리고 이것을 이전에 다익스트라로 구현한 코드에 추가했더니 또 시간이 단축되었다.

생각하는데 도움이 된 질문 게시판 답변 : https://www.acmicpc.net/board/view/10855