[JAVA] 백준 (실버2) 18352번 특정 거리의 도시 찾기

링크

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

---

문제 설명

정답률 30.885%
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

---

입력 예제

• 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)
• 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다.
• 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N)
• 단, A와 B는 서로 다른 자연수이다.

4 4 2 1
1 2
1 3
2 3
2 4

---

출력 예제

• X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
• 이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

4

---

풀이

최단 거리에 관한 문제니까 BFS로 접근한다. 우선 단방향 그래프를 인접 리스트로 구현한다.

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

BFS로 탐색하면서 각 도시로 가는 거리를 저장하고 방문 여부를 체크한다.

while (!queue.isEmpty()) {
    Integer cur = queue.poll();
    for (Integer i : adjList.get(cur)) {
        if (!visited[i]) {
            visited[i] = true;
            queue.add(i);
            dist[i] = dist[cur] + 1;
        }
    }
}

코드

//백준
public class Main {

    static List<List<Integer>> adjList = new ArrayList<>();
    static boolean[] visited;
    static int[] dist;
    static int K;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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());  //도로의 개수
        K = Integer.parseInt(st.nextToken());      //거리 정보
        int X = Integer.parseInt(st.nextToken());  //출발 도시의 번호
        visited = new boolean[N + 1];
        dist = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }

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

        bfs(X);
        //최단 거리가 K인 도시 저장
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            if (dist[i] == K) {
                result.add(i);
            }
        }

        if (result.isEmpty()) {
            System.out.println(-1);
        } else {
            result.forEach(System.out::println);
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            Integer cur = queue.poll();

            for (Integer i : adjList.get(cur)) {
                if (!visited[i]) {
                    visited[i] = true;
                    dist[i] = dist[cur] + 1;  //각 도시로 가는 최단 거리 저장
                    queue.add(i);
                }
            }
        }

    }
}