[백준_18352번] 특정 거리의 도시 찾기

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는 서로 다른 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_18352 {
	static ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
	static int n,m,k,x;
	static int[] d=new int[300001]; // 최단거리 저장 배열
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		m=sc.nextInt();
		k=sc.nextInt();
		x=sc.nextInt();
		
		// 연결리스트에 노드 추가
		for(int i=0;i<=n;i++) {
			graph.add(new ArrayList<Integer>());
			d[i]=-1; // 최단거리 -1로 초기화
		}
		
		// 간선 정보 입력 
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			graph.get(a).add(b);
		}
		
		/*
		 * BFS 알고리즘
		 *  
		 * 모든 도로의 거리가 1이기 때문에 BFS를 사용하여 
		 * 최단거리를 구할 수 있다. 
		 */
		d[x]=0; // 시작지점의 최단거리 값 0으로 초기화
		Queue<Integer> q=new LinkedList<>();
		q.offer(x);
		while(!q.isEmpty()) {
			int now=q.poll();
			
			for(int i=0;i<graph.get(now).size();i++) {
				int next=graph.get(now).get(i);
				if(d[next]==-1) {
					// 도로의 거리가 1이기 때문에 이전 최단거리에 +1한 값 저장
					d[next]=d[now]+1;
					q.offer(next);
				}
			}
		}
		
		// 최단거리가 k인 노드 찾기 
		boolean check=false;
		for(int i=1;i<=n;i++) {
			if(d[i]==k) {
				System.out.println(i);
				check=true;
			}
		}
		
		// 최단거리가 k인 노드가 없다면 -1 출력 
		if(check==false)
			System.out.println(-1);
	}

}

 

[고찰]

 이번 문제는 백준 문제가 이것이 코딩 테스트다 예제 실린 문제이다. 카테고리가 DFS/BFS여서 다익스트라 알고리즘을 사용하지 않고 어떻게 해결해야 하나 고민을 해봤다. 모든 도로의 거리가 1이기 때문에 BFS 알고리즘을 사용할 수 있었다. 시작 노드를 기점으로 하여 연결된 노드는 이전 노드의 거리에서 +1한 값을 최단거리 배열 값으로 갱신하고, 큐에 삽입한다. 해당 과정은 큐가 비지 않는다면 반복하고, 해당 과정이 끝난다면 최단거리 배열에 k와 같은 값이 있다면 해당 인덱스를 출력한다. 

 해당 문제는 물론 다익스트라 알고리즘을 사용하여 풀 수도 있었다. 앞으로 간선간의 거리가 1일 경우에는 BFS로 해결할 수 있다는 것을 기억해두어야겠다.