백준 18352번(특정 거리의 도시 찾기)[JAVA]

풀이

x로부터 최단 경로가 k인 도시를 출력하는 문제이다. 그래프에 익숙치 않는 나는 DFS로 접근했다가 어떻게 고치더라도 예제 입력은 다 맞지만 계속 틀리게 되는 난항을..하였다. 구글링 해본 결과, 이 문제와 같은 최단 경로는 BFS로 푸는게 좋다고 하여 BFS로 접근해보았고, 별 다르게 고친 것 없이 그냥 BFS로만 바꿨을 뿐인데 문제를 맞을 수 있었다…
교훈 : 최단 경로이고, 가중치가 모두 1이면 그냥 BFS를 때려박자!

DFS로 푸는 법 아시는 분…잘 풀어봐도 저(그래프 이제 막 배움)는 안되던데…

소스 코드

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

public class 특정거리의도시찾기 {
	static boolean[] visited;
	static ArrayList<Integer>[] arr;
	static int[] result;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		int x = sc.nextInt();
		
		visited = new boolean[n+1];
		arr = new ArrayList[n+1];
		result = new int[n+1];
		
		for (int i = 1; i < n+1; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			arr[a].add(b);
		}
		
		bfs(x);
		boolean flag = false;
		for (int i = 1; i < n+1; i++) {
			if(result[i] == k) {
				flag = true;
				System.out.println(i);
			}
		}
		if (!flag)
			System.out.println(-1);
	}
	
	static void bfs(int v) {
		Queue<Integer> q = new LinkedList<>();
		q.add(v);
		visited[v] = true;
		
		while (!q.isEmpty()) {
			int now = q.poll();
			for (int i : arr[now]) {
				if (!visited[i]) {
					visited[i] = true;
					result[i] = result[now] + 1;
					q.add(i);
				}
			}
		}
	}
}

태클 감사합니다.
조언 환영입니다.