[Do It! 코딩테스트 자바편(김종관)] 문제 046(백준 18352번)

난이도

나한테는 딱 맞는 수준의 문제였다. 적당히 어렵지만 풀 시도는 할 수 있는 느낌의 문제였다. 물론 푸는 도중 교재 힌트를 본 후에야 코드를 완전히 작성했고, 빨리 실력이 늘면 좋겠다고 생각했다.

문제

특정 거리의 도시 찾기 (백준: 18352번)

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Integer>[] a;
    static List<Integer> answer;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());// 도시 개수
        int m = Integer.parseInt(st.nextToken());// 도로 개수
        int k = Integer.parseInt(st.nextToken());// 최단거리
        int x = Integer.parseInt(st.nextToken());// 시작도시

        answer = new ArrayList<Integer>();
        visited = new int[n + 1];
        for (int i = 1; i < visited.length; i++) {
            visited[i] = -1;
        }

        a = new ArrayList[n + 1];
        for (int i = 1; i < a.length; i++) {
            a[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            a[s].add(e);
        }

        bfs(x);
        for (int i = 1; i < visited.length; i++) {
            if (visited[i] == k) {
                answer.add(i);
            }
        }

        if (answer.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(answer);
            for (int tmp : answer) {
                System.out.println(tmp);
            }
        }
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = 0;
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int tmp : a[node]) {
                if (visited[tmp] == -1) {
                    visited[tmp] = visited[node] + 1;
                    queue.add(tmp);
                }
            }
        }
    }

}