[백준] 특정 거리의 도시 찾기 - Java : 그래프

✓ 문제

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

 

 

그래프들의 단방향 정보가 주어지고 출발 도시로부터 최단 거리가 X인 다른 정점들을 찾는 문제이다.

단순히 거리가 X인 것이 아니라 최단거리여야 한다.

 

 

✓ 풀이

처음에는 DFS탐색을 이용하여 dpeth가 X일 때를 찾았다. 하지만 문제는 최단거리를 구해야 된다는 점이었다. 최단거리를 갱신해주기 위해서는 결국 모든 탐색을 다 해줬어야 했다. 비효율적인 것 같아서 더 효율적인 방법을 찾았다.

 

바로 BFS 탐색을 이용하는 것이다. 매번 잊고 있지만 BFS는 해당 노드를 방문할 때가 최단 거리 또는 최단 값이다! 이 문제도 BFS 탐색을 이용하여 X인 거리를 찾다가 거리가 X를 넘어갈 때 탐색을 그만하면 된다. 

 

주목할 점은 거리 정보를 저장하는 배열과 방문 했는지 정보를 저장하는 배열을 하나로 사용하는 것이다. 일반적으로 나는 2개를 따로 사용하였는데, 이번 풀이에서는 distance 배열을 N+1크기만큼 선언한 후 초기화 값을 -1로 하였다. distance 값이 -1일 때만 방문하지 않은 걸로 간주하여 큐에 넣어 탐색을 진행했다. 탐색을 진행하다 현재 노드의 거리 값이 X를 넘어가면 탐색을 중단한다.

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

public class Main {

    static BufferedWriter bw;
    static BufferedReader br;
    static int K, X, N,M;
    static List<Integer> ans;
    static int [] distance;
    static ArrayList<Integer>[] graph;

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

        br = new BufferedReader(new InputStreamReader(System.in));
        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());

        // 그래프 - 인접 배열
        graph = new ArrayList[N+1];
        for(int i=0; i<graph.length; i++)
            graph[i] = new ArrayList<Integer>();

        // 연결 도로 입력 받기
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            // 단방향 간선 추가
            graph[n1].add(n2);
        }

        ans = new ArrayList<>();
        distance = new int[N+1];
        Arrays.fill(distance, -1);
        bfs(X);

        if(ans.size() == 0){
            bw.write("-1");
        } else{
            Collections.sort(ans);
            for(int node : ans){
                bw.write(node +"\n");
            }
        }
        bw.flush();
        br.close();
        bw.close();

    }
    public static void bfs(int start){
        Queue<Integer> que = new ArrayDeque<>();
        que.add(start);
        distance[start] = 0;

        while(!que.isEmpty()){
            int cur = que.poll();
            if(distance[cur] > K)
                return;
            if(distance[cur] == K){
                ans.add(cur);
                continue;
            }

            for(int child : graph[cur]){
                // 방문을 하지 않았다면
                if(distance[child] == -1){
                    distance[child] = distance[cur] +1;
                    que.add(child);
                }
            }

        }
    }

}