[Java] 백준 17396번: 백도어

[문제 바로 가기] - 백도어

💡 접근 방식

오늘도 다익스트라 문제를 익히기 위해 푼 문제!
일반 다익스트라 풀이에서 1. 시야에 보이지 않을 경우 2. dist의 범위를 고려해서 풀이해야 한다.

Node 클래스를 선언해서 value의 크기에 따라 오름차순 정렬하고 싶다면

class Node implements Comparable<Node> {
	int node;
    long value;
    
    Node (int node, long value) {
    	this.node = node;
        this.value = value;
    }
   	
    @Override
    public int compareTo(Node other) {
    	return Long.compare(this.value, other.value);
    }
}

시간의 최댓값이 100,000이고 N의 최댓값이 100,000이기 때문에 걸린 시간은 최대 100,000 * 100,000이 된다. 이는 int의 범위에서 벗어나므로 dist의 타입을 long으로 설정해주어야 한다. 이걸 몰라서 계속 68%에서 틀렸었는데 문제를 더 풀어서 익숙해져야겠다!

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	static class Node implements Comparable<Node> {
		int node;
        long value;

        Node(int node, long value) {
            this.node = node;
            this.value = value;
        }
        
        @Override
        public int compareTo(Node other) {
        	return Long.compare(this.value, other.value);
        }
	}
	
	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());
		
		boolean isShow[] = new boolean[N];
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			if (Integer.parseInt(st.nextToken()) == 1) isShow[i] = true;
		}
		isShow[N - 1] = false;
		
		List<Node> list[] = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			list[num1].add(new Node(num2, value));
			list[num2].add(new Node(num1, value));
		}
		
		long dist[] = new long[N];
		Arrays.fill(dist, Long.MAX_VALUE);
		
		PriorityQueue<Node> queue = new PriorityQueue<>();
		queue.add(new Node(0, 0));
		dist[0] = 0;
		
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			int node = cur.node;
			long value = cur.value;
			
			if (value > dist[node]) continue;
			
			for (int i = 0; i < list[node].size(); i++) {
				if (!isShow[list[node].get(i).node] &&
						dist[list[node].get(i).node] > dist[node] + list[node].get(i).value) {
					dist[list[node].get(i).node] = dist[node] + list[node].get(i).value;
					queue.add(new Node(list[node].get(i).node, dist[list[node].get(i).node]));
				}
			}
		}
		
		if (dist[N - 1] == Long.MAX_VALUE) System.out.println(-1);
		else System.out.println(dist[N - 1]);
	}
}