[이것이 코딩 테스트다 with Python] 특정 거리의 도시 찾기(Java)

Goal

“이것이 코딩 테스트다 with Python” 교재의 문제를 분석하고 코드와 함께 이해해보기 위한 글입니다.

문제 분석

시작 노드가 주어지고 있으므로 시작 노드에서부터 연결된 노드를 확인해 이전 노드까지의 거리에서 +1 연산을 해 거리값을 갱신하고 큐에 삽입해 BFS를 하고, 특정 거리인지 확인해 출력하는 프로그램을 작성해보도록 하겠습니다.

코드 구현

public class FindSpecificDistance { //p339
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int n, m, k, x;
    static int[] d;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());//출발 도시
        d = new int[n + 1];

        for (int i = 0; i <= n; i++) { //연결리스트에 노드 추가
            graph.add(new ArrayList<>());
            d[i] = -1; //최단거리 초기화
        }
        for (int i = 0; i < m; i++) { //간선 정보 저장
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
        }

        bfs();
    }

    private static void bfs() {
        d[x] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(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) {
                    d[next] = d[now] + 1;
                    q.add(next);
                }
            }
        }

        findNode();
    }

    private static void findNode() {
        boolean check = false;
        for (int i = 1; i <= n; i++) {
            if (d[i] == k) {
                System.out.println(i);
                check=true;
            }
        }

        if (check == false) System.out.println(-1);
    }
}