백준 18352 (Java) 특정 거리의 도시 찾기

풀이

c++ 에선 pair<>형이더라도 pq에서 pair first, second순으로 정렬이 되는데에 반해, 자바는 그렇지 않다.

 

따라서

1. Pair class를 선언해 Pair를 정렬할 수 있는 compareTo를 오버라이딩

2. 오름차순 정렬이 되도록 compareTo를 오버라이딩

하였다.

 

장점으로, 음수화하여 정렬했다가 다시 꺼낼 때 양수화하는 과정이 없어서

코드 작성자의 의도에 맞는 코드를 짤 수 있어 조금이나마 가독성이 좋아졌다고 생각한다.

 

코드

import java.io.*;
import java.lang.reflect.Parameter;
import java.util.*;

public class Main {
    static class Pair implements Comparable<Pair> {
        int cost;
        int node;

        public Pair(int cost, int node) {
            this.cost = cost;
            this.node = node;
        }

        @Override
        public int compareTo(Pair o) {
            return this.cost - o.cost;
        }
    }
    static int n,m,k, x;
    static int[] arr;

    static List<Integer>[] adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj[u].add(v);
        }
        int[] dist = dijkstra(x);
        boolean flag = false;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == k) {
                System.out.println(i);
                flag = true;
            }
        }
        if (!flag) {
            System.out.println(-1);
        }
    }
    static int[] dijkstra (int start) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.offer(new Pair(0, start));
        int[] dist = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int cur = p.node;
            int curCost = p.cost;
            dist[cur] = curCost;
            for (int i = 0; i < adj[cur].size(); i++) {
                int nxt = adj[cur].get(i);
                int nxtCost = curCost + 1;
                if (dist[nxt] > nxtCost) {
                    dist[nxt] = nxtCost;
                    pq.offer(new Pair(nxtCost, nxt));
                }
            }
        }
        return dist;
    }
}