자바(백준) 1719 택배

오답 노트 & 새로 알게 된 점

해당 문제는 다익스트라를 이용하여 풀면 되는데, 

다른 문제와 다른 점은 최소 경로 값을 출력하는 것이 아니라 

가장 먼저 거쳐야 할 노드를 출력하는 것이다.

 

전체적인 풀이를 말하자면

1 ~ N번 노드까지 다익스트라를 구한 뒤, 

각 n번 노드마다 parent를 구하여 정답 배열에 넣어준다.

값을 출력할 때는 행과 열이 같은 지점(대각선) 에는 "-" 을 넣어준다.

 

즉, 1 - 3 - 2가 최소 경로일 때, (1,2)의 값은 3이 된다.

 

1 ~ N번 노드까지 다익스트라를 이용하여 최소 경로를 구하면서,

최소 경로가 갱신될 때마다 즉,

if(dist[node.idx] != node.dist) continue;

if(dist[node.idx] + in.wei >= dist[in.to]) continue;

dist[in.to] = dist[node.idx] + in.wei;
pq.offer(new Node(in.to, dist[in.to]));
parent[in.to] = node.idx;

위 조건을 만족할 때마다 parent 값을 변경시켜주면 된다.

 

parent[i] = j 일 때,

j번 노드를 가기 전에 i번 노드를 거쳐가는 것이다.

즉, j번 노드가 i번 노드의 부모이다.

 

 

부모 값을 찾는 방법

static int find(int v, int start) {
    if(parent[v] == start) return v;

    return find(parent[v], start);
}

find 메서드를 이용하여 부모를 찾는다.

부모는 출발점에서 가장 먼저 거쳐야 하는 노드를 구한다.

 

1 - 3 - 2에서 

parent[1] = 1

parent[2] = 3

parent[3] = 1

 

이 되고,

 

find 메서드를 통해 2번 노드는 3번 노드가 반환되는 것을 알 수 있다.

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int parent[];
    static ArrayList<Info> A[];
    static int N, M;
    static int dist[];
    static int ans[][];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        for (int i = 1; i <= N; i++) {
            dijkstra(i);
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(i == j) {
                    System.out.print("-" + " ");
                    continue;
                }
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2)->{
            return o1.dist - o2.dist;
        });
 
        Arrays.fill(dist, Integer.MAX_VALUE);
        for(int i = 1; i <= N; i++) parent[i] = i;
 
        pq.offer(new Node(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Node node = pq.poll();
 
            for (Info in : A[node.idx]) {
 
                if(dist[node.idx] != node.dist) continue;
 
                if(dist[node.idx] + in.wei >= dist[in.to]) continue;
 
                dist[in.to] = dist[node.idx] + in.wei;
                pq.offer(new Node(in.to, dist[in.to]));
                parent[in.to] = node.idx;
            }
        }
 
        for (int i = 1; i <= N; i++) {
            ans[start][i] = find(i, start);
        }
    }
 
    static int find(int v, int start) {
        if(parent[v] == start) return v;
 
        return find(parent[v], start);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        ans = new int[N+1][N+1];
        dist = new int[N+1];
        parent = new int[N+1];
 
        A = new ArrayList[N+1];
        for (int i = 0; i <= N; i++) A[i] = new ArrayList<>();
 
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
            int wei = atoi(st.nextToken());
 
            A[from].add(new Info(to, wei));
            A[to].add(new Info(from, wei));
        }
    }
 
    static class Info{
        int to, wei;
 
        public Info(int to, int wei) {
            this.to = to;
            this.wei = wei;
        }
    }
 
    static class Node{
        int idx, dist;
 
        public Node(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }
}