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

https://www.acmicpc.net/problem/18352

BFS를 통해 주어진 최단거리 K를 만족하는 도시를 찾는 문제이다. 만약 하나도 존재하지 않을 경우 -1을 출력하라고 했다.

예제 그림을 기준으로 본다면 K = 2, X = 1인 경우 1번 노드를 기준으로 최단거리로 거리가 2인 노드는 4 밖에 없으므로 4를 출력하게 된다.

3번 노드의 경우 [1 -> 2 -> 3]과 같이 이동할 수 있지만, 이는 최단거리가 아니며, 최단거리는 [1 -> 3] == 1이므로 출력하지 않는다.

따라서 우리는 다른 노드로 이동할 때마다 거리 정보를 카운트하기 위해 방문 리스트인 visited를 boolean이 아닌 int 형으로 선언해야 한다.

int[] visited = new int[N + 1];

그 이후 아래와 같이 BFS 탐색을 진행하며 다음으로 방문할 노드에 대해 이전 노드 + 1로 값을 갱신해 주는 것이다.

static void BFS(int v) {
	...
    
    while (!queue.isEmpty()) {
            int nowNode = queue.poll();

            for (int i : A[nowNode]) {
                if (visited[i] == -1) {
                    queue.add(i);
                    visited[i] = visited[nowNode] + 1;
                }
            }
        }
	...

예제 입력을 기준으로 코드를 실행한다면, BFS 탐색을 수행한 visited 배열의 결과는 아래와 같다.

visited = [0, 0, 1, 1, 2]

1번 노드를 시작노드로 선택하였으니 0으로 설정하고, 이후 BFS를 통해 다음 노드로 건너갈때마다 +1이 추가된다.

따라서 전체 소스코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P_18352 {
    static int[] visited;
    static ArrayList<Integer>[] A;
    static int N, M, K, X;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        visited = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            visited[i] = -1;
        }

        A = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            A[start].add(end);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(A[i]);
        }

        BFS(X);

        boolean found = false;
        for (int i = 1; i <= N; i++) {
            if (visited[i] == K) {
                found = true;
                System.out.println(i);
            }
        }

        if (!found) System.out.println(-1);
    }

    static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(v);
        visited[v] = 0;

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

            for (int i : A[nowNode]) {
                if (visited[i] == -1) {
                    queue.add(i);
                    visited[i] = visited[nowNode] + 1;
                }
            }
        }
    }
}