[백준 / BOJ] 17396번 : 백도어 - JAVA

https://www.acmicpc.net/problem/17396

17396번: 백도어

Dijkstra 알고리즘과 Priority Queue

보통 다익스트라 알고리즘을 사용할 때 우선 순위 큐보다는 for문을 사용했는데, 이번 문제는 거리가 가장 작은 노드를 매번 찾으면 시간 초과가 났다. N의 최대 값이 100,000이기 때문에 for문으로 dist 배열을 돌리면서 거리가 가장 짧은 노드를 찾는다면 최대 10,000,000,000번 조사하게 된다.

 

하지만 그렇다고 우선순위 큐가 월등히 빠를 거라곤 생각하지 않았는데, 방법을 바꾸니까 시간 초과에서 벗어날 수 있었다. (찾아보니 우선순위 큐를 사용한 경우 O(N^2)가 아니라 O(MlogN)이 걸린다고 한다)

 

그 외에도 시간을 줄이기 위해 N - 1이 아니면서 적의 시야에 보이는 노드가 포함된 경로는 아예 받지 않았다.

 

전체 코드

// 시간 : 924ms
// 메모리 : 146220KB
public class Main {

	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[] watch = new int[N];
		List<int[]>[] list = new ArrayList[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			watch[i] = Integer.parseInt(st.nextToken());
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			
			if(watch[a] == 1 && a != N - 1) continue;
			if(watch[b] == 1 && b != N - 1) continue;
			list[a].add(new int[] {b, t});
			list[b].add(new int[] {a, t});
		}
		
		System.out.println(dijkstra(list, watch));
	}

	static class Node implements Comparable<Node> {

		int next;
		long cost;
		
		public Node(int next, long cost) {
			super();
			this.next = next;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) {
			return Long.compare(this.cost, o.cost);
		}
		
	}
	private static long dijkstra(List<int[]>[] list, int[] watch) {

		int N = list.length;
		long[] dist = new long[N];
		Arrays.fill(dist, Long.MAX_VALUE);
		PriorityQueue<Node> que = new PriorityQueue<>();
		que.offer(new Node(0, 0));
		dist[0] = 0;
		
		while (!que.isEmpty()) {
			Node cur = que.poll();
			
			if(cur.cost >= dist[N - 1]) continue;
			if(cur.cost > dist[cur.next]) continue;
			
			for (int[] i : list[cur.next]) {
				if(dist[i[0]] > cur.cost + i[1]) {
					dist[i[0]] = cur.cost + i[1];
					que.add(new Node(i[0], dist[i[0]]));
				}
			}
		}
		
		return dist[N - 1] == Long.MAX_VALUE ? -1 : dist[N - 1];
	}


}