문제 링크 http://acm.kaist.ac.kr/2008/ProblemSet.pdf , C - Homing
문제 설명
어떤 사람이 출발지에서부터 목적지까지 자동차를 운전해서 가려고 합니다. 출발지와 목적지 사이에는 여러 도시들이 있고 서로 연결된 도시간의 거리 정보( = 그 길을 가는 데에 쓰이는 연료량)가 주어집니다. 이 사람은 출발지에서부터 목적지까지 가는 데에 필요한 최소한의 연료만을 넣어서 출발하고 싶습니다. 그러나 한 가지 문제가 있는데, 이 사람이 목적지를 향하던 도중에 기존에 존재하던 연결 중 최대 한 쌍 도시의 연결이 끊어질 수 있습니다. 그런데 이 사람은 그 연결이 끊어졌다는 것을 연결이 끊어진 끊어진 도시에 도착하였을 때 알 수 있습니다. 위와 같은 사실을 명심하며, 이 사람이 최소한 얼마나 많은 연료를 출발점에서 넣어야만 도착점에 무사히 도착할 수 있을까요? 도시의 숫자와 도시간 연결의 숫자는 모두 1이상 만 이하입니다. 모든 연결쌍이 무사할 경우의 최단거리 경로 역시 입력으로 주어집니다.
문제 풀이
[spoiler="더 보기..."]최대 한 쌍의 도로에 사고가 생길 수 있다는 사실에 주목해 보겠습니다.
i) 만약 사고가 생긴 도로가 최단경로상에 있는 도로가 아니라면?
이 때 여행자는 최단경로에서 필요한 연료만을 준비해서 가면 됩니다.
ii) 만약 사고가 생긴 도로가 최단경로상에 있는 도로 중 하나라면?
최단경로가 도시 s a b c d e t 를 순서대로 여행하는 것이라 가정하겠습니다. 만약에 b와 c를 연결하는 도로에 사고가 생겼다면, 여행자는 도시 b에 도착하였을 당시에 그 사실을 알 수 있습니다. 그럼 이 사실을 알아차린 시점에서 여행자가 도착지까지 가장 빠르게 갈 수 있는 방법은 b-c를 거치지 않으면서, b에서 가능한 가장 빠르게 t로 갈 수 있는 경로를 찾아보는 것입니다. 즉 이 문제는 b-c 의 거리가 무한대일 때 b에서 t까지의 최단경로를 찾는 것과 같습니다. 그 후에 s부터 b까지 가는 길에 걸리는 연료량을 더해준다면 b-c 도로에 사고가 생겼을 시 전체 여행에 필요한 최소의 연료량을 구할 수 있습니다. 위와 같은 방법을 s-a 도로에 사고가 생겼을 때, a-b 도로에 사고가 생겼을 때, ... e-t 도로에 사고가 생겼을 때를 각각 가정하여 최단거리를 계산해 보고, 그 최단거리중 가장 큰 값을 여행자가 필요한 최소의 연료량으로 생각하면 문제는 해결됩니다.
사고가 생긴 도로의 인접도시에 도착하였을 때, 현재 도시에서 도착지까지의 최단 거리는 다익스트라를 통해서 구할 수 있습니다( O(VlgE) ). 이 다익스트라를 최단경로상에 있는 모든 도로의 갯수번 수행해야 함으로 다익스트라를 최대 (V-1)번 수행해야 합니다. 고로 본 풀이의 시간복잡도는 O(V^2lgE)입니다.
사실 저는 대회 당시에 이 문제를 해결하지 못하였기 때문에 본 풀이가 실제 데이터에서 올바르게 작동할지 확신하지는 못합니다. 다만 YES를 받았던 팀 선수의 말에 따르면 이 풀이와 같은 시간복잡도로 실제 대회에서는 통과되었다고 합니다. 이 풀이 외에도 다른 풀이가 있다면 들어보고싶네요~[/spoiler]
코드
VOCList
문제 링크
http://acm.kaist.ac.kr/2008/ProblemSet.pdf , C - Homing
문제 설명
어떤 사람이 출발지에서부터 목적지까지 자동차를 운전해서 가려고 합니다. 출발지와 목적지 사이에는 여러 도시들이 있고 서로 연결된 도시간의 거리 정보( = 그 길을 가는 데에 쓰이는 연료량)가 주어집니다. 이 사람은 출발지에서부터 목적지까지 가는 데에 필요한 최소한의 연료만을 넣어서 출발하고 싶습니다. 그러나 한 가지 문제가 있는데, 이 사람이 목적지를 향하던 도중에 기존에 존재하던 연결 중 최대 한 쌍 도시의 연결이 끊어질 수 있습니다. 그런데 이 사람은 그 연결이 끊어졌다는 것을 연결이 끊어진 끊어진 도시에 도착하였을 때 알 수 있습니다. 위와 같은 사실을 명심하며, 이 사람이 최소한 얼마나 많은 연료를 출발점에서 넣어야만 도착점에 무사히 도착할 수 있을까요? 도시의 숫자와 도시간 연결의 숫자는 모두 1이상 만 이하입니다. 모든 연결쌍이 무사할 경우의 최단거리 경로 역시 입력으로 주어집니다.
문제 풀이
[spoiler="더 보기..."]최대 한 쌍의 도로에 사고가 생길 수 있다는 사실에 주목해 보겠습니다.
i) 만약 사고가 생긴 도로가 최단경로상에 있는 도로가 아니라면?
이 때 여행자는 최단경로에서 필요한 연료만을 준비해서 가면 됩니다.
ii) 만약 사고가 생긴 도로가 최단경로상에 있는 도로 중 하나라면?
최단경로가 도시 s a b c d e t 를 순서대로 여행하는 것이라 가정하겠습니다. 만약에 b와 c를 연결하는 도로에 사고가 생겼다면, 여행자는 도시 b에 도착하였을 당시에 그 사실을 알 수 있습니다. 그럼 이 사실을 알아차린 시점에서 여행자가 도착지까지 가장 빠르게 갈 수 있는 방법은 b-c를 거치지 않으면서, b에서 가능한 가장 빠르게 t로 갈 수 있는 경로를 찾아보는 것입니다. 즉 이 문제는 b-c 의 거리가 무한대일 때 b에서 t까지의 최단경로를 찾는 것과 같습니다. 그 후에 s부터 b까지 가는 길에 걸리는 연료량을 더해준다면 b-c 도로에 사고가 생겼을 시 전체 여행에 필요한 최소의 연료량을 구할 수 있습니다. 위와 같은 방법을 s-a 도로에 사고가 생겼을 때, a-b 도로에 사고가 생겼을 때, ... e-t 도로에 사고가 생겼을 때를 각각 가정하여 최단거리를 계산해 보고, 그 최단거리중 가장 큰 값을 여행자가 필요한 최소의 연료량으로 생각하면 문제는 해결됩니다.
사고가 생긴 도로의 인접도시에 도착하였을 때, 현재 도시에서 도착지까지의 최단 거리는 다익스트라를 통해서 구할 수 있습니다( O(VlgE) ). 이 다익스트라를 최단경로상에 있는 모든 도로의 갯수번 수행해야 함으로 다익스트라를 최대 (V-1)번 수행해야 합니다. 고로 본 풀이의 시간복잡도는 O(V^2lgE)입니다.
사실 저는 대회 당시에 이 문제를 해결하지 못하였기 때문에 본 풀이가 실제 데이터에서 올바르게 작동할지 확신하지는 못합니다. 다만 YES를 받았던 팀 선수의 말에 따르면 이 풀이와 같은 시간복잡도로 실제 대회에서는 통과되었다고 합니다. 이 풀이 외에도 다른 풀이가 있다면 들어보고싶네요~[/spoiler]
코드
15년 전