BOJ_18352 : 특정 거리의 도시 찾기

👉 문제링크

18352번: 특정 거리의 도시 찾기

---

🔸 문제 분석 🔸

• N개의 도시와 도시 사이를 연결하는 M개의 단방향 도로가 존재한다.
  • 도로 하나 당 1의 거리를 갖는다.
• X번 도시에서 시작해 최단거리가 정확히 X 거리만큼 떨어진 도시의 목록을 출력한다.

🔸 문제 풀이 🔸

• 하나의 노드에서 다른 모든 노드들의 최단 거리를 구해야 하므로 다익스트라 알고리즘을 사용한다.
  • N은30만개인데, 우선순위 큐를 활용해 O(NlogN)으로 해결하면, 약 16억(1.6초)으로 제한시간 2초에 충분하다.
• 간선이 100만개 이면서 간선 당 1의 가중치를 가지므로 int형으로 충분하다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    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());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        int[] city = new int[N + 1];
        ArrayList<Integer>[] adjList = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            city[i] = Integer.MAX_VALUE;
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            adjList[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
        }

        Queue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(X, X, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (city[edge.end] > edge.cost) {
                city[edge.end] = edge.cost;

                for (int i : adjList[edge.end]) {
                    pq.add(new Edge(edge.end, i, edge.cost + 1));
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            if (city[i] == K) {
                sb.append(i).append('\n');
            }
        }
        if (sb.length() == 0) {
            sb.append(-1);
        }

        bw.write(sb.toString().trim());
        bw.flush();
    }

    private static class Edge implements Comparable<Edge> {
        int start, end, cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }
}

🔸 코드 해석 🔸

• 간선 저장을 위한 Edge 클래스를 만들어, 시작과 끝 노드 번호와 가중치를 저장해 사용했다.
• 간선 정보는 ArrayList배열 adjList에 저장해 사용했다.
• X에서 X로 가는 거리는 0이라고 했으므로, 우선순위 큐에 시작 값으로 넣고 다익스트라 알고리즘을 실행한다.
  • 저장된 최단 거리보다 작은 값이 나오면, 값을 갱신하고 다시 연결된 간선 정보를 큐에 넣어 확인한다.
• 모든 거리를 계산 후, 값이 K인 노드 번호를 출력한다.

---

🔸 end 🔸

•  빌드 했을 때는 잘 됐는데, 제출해보니 StringBuilder 부분에 컴파일 에러가 났다.
  • 기존 코드는 sb.isEmpty()이면 sb.append(-1)을 넣는 방식으로, 거리가 K인 도시가 없으면 -1을 넣고자 했다.
  • 하지만 isEmpty()이후에 append를 사용하는게 백준 컴파일러에서는 에러가 나는듯 하다.
  • sb.length()가 0인지 확인하는 코드로 변경했다.