BOJ - 11779

BOJ - 11779

(문제 : https://www.acmicpc.net/problem/11779)

재채점 결과 저격당한 문제

답은 맞았지만 시간초과가 나는 상태였음. 재채점 후 그냥 틀린 문제는 많았지만 이런 경우는 처음이어서 해결방법을 찾을 수 없는 상태였다.

문제 해결 방법

평범한 다익스트라 문제지만 틀린이유

먼저 해당 블로그를 참고하였음.(http://www.secmem.org/blog/2019/01/09/wrong-dijkstra/)
애초에 다익스트라를 잘못 구현할 경우 같은 vertex를 여러 번 방문하는 경우가 있다. 해결 방법은 vertex를 여러 번 방문하지 않도록 설정하는 것이다.

기존 코드의 문제점

// 앞부분 생략
PriorityQueue<Node> q = new PriorityQueue<>();

q.add(new Node(S, 0));
d[S] = 0;
num[S] = 1;
str[S] = S + " ";

while(!q.isEmpty()) {
    Node cur = q.poll();
    int curNode = cur.end;
    int curWeight = cur.weight;

    visited[curNode] = true; // 이 부분에서 visited를 확인하지 않음.

    for(int i = 0; i < list[curNode].size(); i++) {
        int nextNode = list[curNode].get(i).end;
        int nextWeight = list[curNode].get(i).weight;

        if(!visited[nextNode] && d[nextNode] > curWeight + nextWeight) {
            d[nextNode] = curWeight + nextWeight;
            str[nextNode] = str[curNode] + nextNode + " ";
            num[nextNode] = num[curNode] + 1;

        	q.add(new Node(nextNode, d[nextNode]));
    	}
    }
}
// 뒷 부분 생략		

해결 및 최종 코드

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

public class Main {
	public static class Node implements Comparable<Node> {
		int end;
		int weight;
		
		Node (int end, int weight) {
			this.end = end;
			this.weight = weight;
		}
		
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
	}
	public static final int INF = 100_000 * 1000;
	public static ArrayList<Node> list[];
	public static boolean[] visited;
	public static int[] d, num;
	public static String[] str;
	public static int N, M, S, E, W;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		list = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		d = new int[N + 1];
		num = new int[N + 1];
		str = new String[N + 1];
		
		Arrays.fill(d, INF);
		
		for(int i = 0; i <= N; i++)
			list[i] = new ArrayList<>();
		
		while(M --> 0) {
			st = new StringTokenizer(br.readLine());
			
			S = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			
			list[S].add(new Node(E, W));
		}
		
		st = new StringTokenizer(br.readLine());
		
		S = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		PriorityQueue<Node> q = new PriorityQueue<>();
		
		q.add(new Node(S, 0));
		d[S] = 0;
		num[S] = 1;
		str[S] = S + " ";
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			int curNode = cur.end;
			int curWeight = cur.weight;
			
			if(visited[curNode]) continue;
			visited[curNode] = true;
			
			for(int i = 0; i < list[curNode].size(); i++) {
				int nextNode = list[curNode].get(i).end;
				int nextWeight = list[curNode].get(i).weight;
				
				if(!visited[nextNode] && d[nextNode] > curWeight + nextWeight) {
					d[nextNode] = curWeight + nextWeight;
					str[nextNode] = str[curNode] + nextNode + " ";
					num[nextNode] = num[curNode] + 1;
					
					q.add(new Node(nextNode, d[nextNode]));
				}
			}
		}
		
		System.out.println(d[E]);
		System.out.println(num[E]);
		System.out.println(str[E]);
	}

}

후기

예전에 풀었던 문제지만 다익스트라를 다시 한 번 정확하게 짚고 넘어가야겠다고 생각하게 된 문제이다.
이런걸 저격하는 사람은 대단한 사람인듯..(feat. djm03178)