BOJ 18532 특정 거리의 도시 찾기 (Java)

문제 탐색하기

•  1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다.
• 모든 도로의 거리는 1
• 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하라.
• X에서 X로 가는 최단 거리는 항상 0이다.

코드 설계하기

전형적인 BFS 알고리즘 문제이다.

이 문제는 모든 도로의 거리가 1로 동일하므로 BFS(너비 우선 탐색)를 사용하여 최단 거리를 구할 수 있다.
BFS는 시작점에서 가까운 노드부터 차례대로 탐색하며, 방문한 노드의 거리를 현재 노드 거리 +1로 갱신한다.

1. 큐(Queue) 활용: FIFO(First-In-First-Out) 방식으로 노드를 탐색한다.
2. 거리 배열 사용: 방문 여부와 최단 거리를 저장한다.
3. 단방향 그래프 탐색: 인접 노드를 방문하면서 거리를 업데이트한다.

구현 방법

1. 그래프 입력: 인접 리스트 (List<List<Integer>>)를 사용하여 노드를 저장한다.
2. 거리 배열 초기화: 거리 값을 저장하는 distance[] 배열을 -1로 초기화한다.
3. BFS 탐색 시작:
   • 출발 도시 X를 큐에 추가하고 거리 0으로 설정한다.
   • 큐에서 노드를 하나씩 꺼내면서 연결된 노드를 방문한다.
   • 방문하지 않은 노드는 현재 거리 + 1로 갱신하고, 큐에 추가한다.
4. 결과 출력:
   • K 거리만큼 떨어진 도시를 오름차순으로 출력한다.
   • 도달할 수 있는 도시가 없다면 -1을 출력한다.

시간 복잡도

• BFS의 시간 복잡도: O(N + M)
  • N: 도시(노드) 개수
  • M: 도로(간선) 개수
• BFS에서 각 노드는 최대 한 번 방문하므로 O(N), 각 간선을 확인하는 과정이 O(M)이므로, 전체 복잡도는 O(N + M)
• 2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000 이므로 시간 내에 충분히 해결이 가능하다.

정답 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    private static int N, M, K, X ;
    private static List<List<Integer>> nodes = new ArrayList<>();
    private static int[] distance;

    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());

        // 현재 노드의 간선 정보 초기화
        for (int i = 0; i <= N; i++) {
            nodes.add(new ArrayList<>());
        }

        // X를 출발 지점으로 한 거리 정보 배열
        distance = new int[N + 1];
        Arrays.fill(distance, -1);

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 단방향 노드
            nodes.get(a).add(b);
        }

        BFS();

        boolean flag = false;
        for (int i = 1; i <= N; i++) {
            if(distance[i] == K){
                bw.write(i + "\n");
                flag = true;
            }
        }

        if (!flag) {
            bw.write("-1\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void BFS() {
        Queue<Integer> queue = new LinkedList<>();
        // 출발 위치를 지정한다.
        queue.add(X);
        distance[X] = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            // 다음 노드 정보를 꺼내온다.
            for (int next : nodes.get(node)) {
                if (distance[next] == -1) {
                    // 거리 정보를 업데이트하고, 큐에 다음 노드를 추가한다.
                    distance[next] = distance[node] + 1;
                    queue.add(next);
                }
            }
        }
    }
}