[Do It! 코딩테스트 자바편(김종관)] 문제 056(백준 1753번)

느낀점

• 이 문제 처음 풀고 제출했을 때 틀려서 교재 풀이를 봤다.
• 만약 다시 이 문제 풀 때 지금처럼 틀리고 왜 틀린지 모르겠으면, 다음 케이스 입력하고 디버그해 보면 이해 얼추 된다. 아래 케이스는 교재 다익스트라 이론 부분에서 설명할 때 쓰는 케이스이다.

5 6
1
1 2 8
1 3 3
2 4 4
2 5 15
3 4 13
4 5 2

문제

최단경로 (백준: 1753번)

풀이

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

public class Main {
    static ArrayList<Node>[] list;
    static int[] shortestPaths;
    static boolean[] visited;
    static PriorityQueue<Node> queue = new PriorityQueue<>();

    static int startNode;
    static int nodeNum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeNum = Integer.parseInt(st.nextToken());
        int edgeNum = Integer.parseInt(st.nextToken());
        startNode = Integer.parseInt(br.readLine());
        visited = new boolean[nodeNum + 1];
        list = new ArrayList[nodeNum + 1];
        shortestPaths = new int[nodeNum + 1];

        // 인접리스트와 최단 경로 배열 초기화하기
        for (int i = 1; i <= nodeNum; i++) {
            if (i == startNode) {
                shortestPaths[i] = 0;
            } else {
                shortestPaths[i] = Integer.MAX_VALUE;
            }

            list[i] = new ArrayList<>();
        }

        // 인접리스트에 값 넣기
        for (int i = 1; i <= edgeNum; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[s].add(new Node(e, w));
        }

        dijkstra();
        diplayAnswer();
    }

    private static void dijkstra() {
        queue.add(new Node(startNode, shortestPaths[startNode]));

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if (visited[now.nodeNum])
                continue;
            visited[now.nodeNum] = true;

            for (Node next : list[now.nodeNum]) {
                if (shortestPaths[next.nodeNum] > shortestPaths[now.nodeNum] + next.w) {
                    shortestPaths[next.nodeNum] = shortestPaths[now.nodeNum] + next.w;
                    queue.add(new Node(next.nodeNum, shortestPaths[next.nodeNum]));
                }
            }
        }
    }

    private static void diplayAnswer() {
        for (int i = 1; i <= nodeNum; i++) {
            if (visited[i]) {
                System.out.println(shortestPaths[i]);
            } else {
                System.out.println("INF");
            }

        }
    }
}

class Node implements Comparable<Node> {
    int nodeNum;
    int w;

    public Node(int nodeNum, int w) {
        this.nodeNum = nodeNum;
        this.w = w;
    }

    @Override
    public int compareTo(Node n) {
        return this.w - n.w;
    }
}