[백준] 18352번 : 특정 거리의 도시 찾기 - Java

문제

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

주어진 그래프에서 특정 도시 X로부터 출발하여, 정확히 K 만큼 떨어져 있는 모든 도시를 찾는 문제입니다. 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 X가 주어지며, 각 도로는 단방향입니다. 도시를 정확히 K만큼 이동하여 도달할 수 있는 도시들을 출력하고, 만약 그런 도시가 없다면 -1을 출력합니다.

접근 방법

문제는 그래프 탐색 문제로, 너비 우선 탐색(BFS)을 사용하여 해결할 수 있습니다. BFS는 모든 간선의 가중치가 동일한 상황에서 최단 거리를 찾는데 효과적입니다. 우리는 BFS를 사용하여 출발 도시 X로부터 모든 도시까지의 최단 거리를 구하고, 이 중에서 거리 K인 도시들을 출력하면 됩니다.

구현

• 그래프 초기화: 도시의 개수 N을 기반으로 그래프를 인접 리스트 형태로 초기화합니다.
• 간선 정보 입력: 주어진 도로 정보를 바탕으로 그래프에 간선을 추가합니다.
• 거리 배열 초기화: 모든 도시의 거리를 -1로 초기화하고, 출발 도시의 거리를 0으로 설정합니다.
• BFS 수행: 큐를 사용하여 BFS를 수행하고, 각 도시의 최단 거리를 계산합니다.
• 결과 출력: 거리 K인 모든 도시를 오름차순으로 출력하고, 그런 도시가 없으면 -1을 출력합니다.

코드

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

public class Main {
    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());

        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = 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());
            graph[a].add(b);
        }

        int[] distance = new int[n + 1];
        Arrays.fill(distance, -1);
        distance[x] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);

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

            for (int next : graph[current]) {
                if (distance[next] == -1) {
                    distance[next] = distance[current] + 1;
                    queue.add(next);
                }
            }
        }

        boolean found = false;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == k) {
                System.out.println(i);
                found = true;
            }
        }

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

 

메모리:277068kb 시간:1240ms