문제
유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.
최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다. 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.
입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.
입력
첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 <= N <= 100,000, 1 <= M <= 300,000)
두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a₀, a₁, ..., aₙ₋₁가 공백으로 구분되어 주어진다. aᵢ가 0이면 i번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a₀ = 0, aₙ₋₁ = 1이다. N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.
다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. 이는 a번과 b번 분기점을 연결하는 양방향 길을 지나가는 데 t만큼의 시간이 걸린다는 뜻이다.
풀이
그래프 자체는 일반 최단 경로 문제지만, 시야에 걸리는 정점은 중간에 지나갈 수 없다는 조건이 있다. 그래서 애초에 그런 정점으로 들어가는 간선을 그래프에 넣지 않는 방식이 편하다.
코드에서는 vision[i] == 1인 정점은 목적지가 아닌 이상 그래프에서 제외한 것처럼 처리한다. 이후에는 남은 그래프에 대해 다익스트라를 그대로 수행하면 된다.
가중치 합이 커질 수 있어서 거리 배열과 우선순위 큐의 비용은 long으로 관리한다.
중요한 예외는 마지막 정점이다. 도착 지점은 시야에 보이더라도 반드시 들어가야 하므로, 코드에서도 vision[N - 1] = 0으로 강제로 바꿔 놓고 그래프를 만든다. 이 처리를 빼면 도착 자체가 막혀 버릴 수 있다.
결국 핵심은 "못 가는 정점을 탐색 중에 걸러내는 것"이 아니라 "그래프를 만들 때부터 제거하는 것"이다. 그렇게 전처리해 두면 이후 로직은 평범한 다익스트라와 다르지 않다.
코드
import java.io.*;
import java.util.*;
public class Main {
static class Edge implements Comparable<Edge> {
int to;
long weight;
Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.weight, o.weight);
}
}
static ArrayList<Edge>[] route;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] vision = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
vision[i] = Integer.parseInt(st.nextToken());
vision[N - 1] = 0;
route = new ArrayList[N];
for (int i = 0; i < N; i++)
route[i] = new ArrayList<>();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
if (vision[b] == 0) route[a].add(new Edge(b, t));
if (vision[a] == 0) route[b].add(new Edge(a, t));
}
System.out.println(solve(N));
}
static long solve(int N) {
long[] dist = new long[N];
Arrays.fill(dist, Long.MAX_VALUE);
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(0, 0));
dist[0] = 0;
while (!pq.isEmpty()) {
Edge cur = pq.poll();
if (dist[cur.to] < cur.weight) continue;
for (Edge next : route[cur.to]) {
if (dist[next.to] > cur.weight + next.weight) {
dist[next.to] = cur.weight + next.weight;
pq.offer(new Edge(next.to, cur.weight + next.weight));
}
}
}
if (dist[N - 1] == Long.MAX_VALUE) return -1;
return dist[N - 1];
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
다익스트라 자체는 평범하지만, 갈 수 없는 정점을 미리 그래프에서 제거해 버리면 훨씬 깔끔하다. 조건 전처리가 핵심인 문제다.
