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

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

 

특정 거리의 도시 찾기

 

문제

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

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

입력

첫째 줄에 도시의 개수 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는 서로 다른 자연수이다.

출력

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

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

4

 

---

풀이

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

public class Main {
    static int N; // 도시 개수
    static int E; // 에지 개수
    static int K; // 최단거리
    static int S; // 출발 도시번호
    static int[] depth; // 거리기록 배열
    static ArrayList<Integer>[] A;

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()); // 1번째 줄 읽음

        N = Integer.parseInt(st.nextToken()); // 도시 개수(노드)
        E = Integer.parseInt(st.nextToken()); // 도로개수(에지)
        K = Integer.parseInt(st.nextToken()); // 최단거리 (depth)
        S = Integer.parseInt(st.nextToken()); // 출발도시 번호(start node)

        depth = new int[N+1]; // 도시번호 1번부터 시작
        A = new ArrayList[N+1]; // 노드와 인접리스트 기록

        // depth 배열 -1로 초기화
        Arrays.fill(depth, -1);

        // 노드 별로 인접리스트 만들어주기
        for(int i=1; i<N+1; i++){
            A[i] = new ArrayList<>();
        }

        // 인접노드리스트 값 넣어주기 (에지 개수만큼)
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            A[node1].add(node2); // 단방향 간선
        }

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

        // 시작노드 S부터 BFS 시작
        BFS(S);

        // BFS 모두 순회 후 거리가 K인 도시만 출력
        ArrayList<Integer> answer = new ArrayList<>();
        for(int i=1; i<N+1; i++){
            if(depth[i] == K){
                answer.add(i);
            }
        }

        // 정답리스트 오름차순 정렬
        Collections.sort(answer);
        if(!answer.isEmpty()){
            // answer 리스트가 비지 않았다면 도시번호 값 출력
            for(int i=0; i<answer.size(); i++){
                System.out.println(answer.get(i));
            }
        }else{
            System.out.println("-1");
        }

    }

    private static void BFS(int S){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(S); // 출발도시번호 넣기
        depth[S]++; // 출발 depth 0 시작

        while (!queue.isEmpty()){
            // queue가 빌 때까지 수행
            int now = queue.poll(); // 현재 노드

            for(int next : A[now]){ // 현재노드의 인접리스트 순회
                if(depth[next] == -1){
                    // 만약 한번도 방문하지 않은 노드라면 큐에 넣어준다.
                    queue.offer(next);
                    depth[next] = depth[now] + 1; // 이전 노드 depth에 1추가 (도로거리 무조건 1)
                }
            }
        }
    }
}

 

• BFS, 그래프를 활용한 문제
• 도시번호가 1번부터 시작하므로 N+1크기의 ArrayList와 depth배열을 선언해준다.
• 인접리스트를 활용해서 노드와 인접노드의 입력값을 받아준다.
  • 단방향 도로임을 유의한다. 
  • for문을 순회하면서 노드의 인접노드를 오름차순으로 정렬해준다.
• BFS문을 수행하면서 depth를 계산한다.
  • 다음 노드의 depth는 이전노드 depth+1이다.
• BFS문을 모두 수행하고 depth배열을 순회하면서
  • depth == K 인 노드번호(도시번호 이름)을 찾는다.
  • 찾았다면 새로운 ArrayList answer에 add 해준다.
• 만약 answer 리스트가 비어있다면 -1 출력
• 비어있지 않다면 줄바꿈하면서 출력