[BOJ] 18352 특정 거리의 도시 찾기_JAVA

 

[문제]

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

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

어떤 나라에는 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는 서로 다른 자연수이다.

[출력]

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

 

---

[Solution]
- BFS(너비우선탐색) 문제
- N은 최대 300,000 M은 최대 1,000,000 이므로 시간복잡도 O(1,300,000)

package boj18352_특정거리의도시찾기;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      
      int n = s.nextInt();   //도시의 개수
      int m = s.nextInt();   //도로의 개수
      int k = s.nextInt();   //거리 정보
      int x = s.nextInt();   //출발 도시의 번호
      
      int[] distance = new int[300001];
      ArrayList<ArrayList<Integer>> linkLst = new ArrayList<ArrayList<Integer>>();
      
      //INIT link list & distance Array
      for(int i=0; i<=n; i++) {
         linkLst.add(new ArrayList<Integer>());
         distance[i] = -1;
      }
      
      distance[x] = 0;   //출발도시->출발도시 거리
      
      for(int i=0; i<m; i++) {
         int a = s.nextInt();
         int b = s.nextInt();
         
         linkLst.get(a).add(b);   //a->b 단방향
      }
      
      //BFS
      Queue<Integer> queue = new LinkedList<Integer>();
      queue.add(x);         //출발도시x
      
      while(!queue.isEmpty()) {
         int tmp = queue.poll();
         
         for(int i=0; i<linkLst.get(tmp).size(); i++) {
            int next = linkLst.get(tmp).get(i);
            
            //방문한적 없으면
            if(distance[next] == -1) {
               distance[next] = distance[tmp]+1;   //출발도시에서 next도시까지 거리
               queue.add(next);
            }
         }
      }
      
      //최단거리==k check, 도시번호 print
      boolean chk = false;
      for(int i=0; i<=n; i++) {
         if(distance[i] == k) {
            System.out.println(i);
            chk = true;
         }
      }
      if(!chk) System.out.println(-1);
   }
}