백준 18352 특정 거리의 도시 찾기

문제

풀이

public class Q18352_특정거리도시찾기 {

    // 각 노드의 연결 정보를 저장할 배열
    static ArrayList<Integer>[] arr;

    // 방문 노드의 깊이를 저장할 배열
    static int[] visited;

    // 깊이가 k이상인 노드를 저장할 배열
    static List<Integer> result;

    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());

        // 노드 배열과 방문 배열 초기화
        visited = new int[n + 1];
        arr = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
            // 모든 노드의 배열 정보를 -1로 초기화
            visited[i] = -1;
        }

        // 각 엣지 정보 입력
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
        }
        // 너비 우선 탐색 시작
        bfs(x);

        // 깊이가 k이상인 노드를 저장할 배열 초기화
        result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            // 노드 i의 깊이가 k 이상이면 result에 추가
            if (visited[i] == k) {
                result.add(i);
            }
        }

        // result가 비었다면 깊이가 k인 노드가 없다는 말이므로 -1 출력
        if (result.isEmpty()) {
            System.out.println(-1);
        // 아니라면
        } else {
            // 오름차순으로 깊이가 k인 노드를 모두 출력해야 하므로 정렬
            Collections.sort(result);
            for (int i : result) {
                System.out.println(i);
            }
        }
    }

    public static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        // 시작 노드를 큐에 먼저 집어 넣고
        q.add(node);
        // 시작 노드의 깊이를 1증가 시킴
        visited[node]++;
        while (!q.isEmpty()) {
            int now = q.poll();
            // 현재 노드와 연결된 노드를 탐색
            for (int i : arr[now]) {
                // 현재 노드와 연결된 각 노드를 방문하지 않았다면
                if (visited[i] == -1) {
                    // 연결된 노드를 큐에 추가하고
                    q.add(i);
                    // 연결된 노드의 깊이를 현재 노드의 깊이 + 1로 저장
                    // 이렇게 함으로
                    visited[i] = visited[now] + 1;
                }
            }
        }
    }
}

리뷰

문제에 최단거리를 구하라고 한 것을 보면 bfs를 활용하는 문제임을 알 수 있다.
다만 최단거리가 k인 모든 도시를 구하라고 하였으므로 따로 거리가 k인 도시를 체크해야 한다.
따라서 기존에 방문 여부를 체크했던 boolean형 배열을 int형으로 선언하여 현재 방문한 도시의 깊이(또는 거리)를 저장해주는 아이디어가 필요하다.

위 문제의 흐름을 살펴보면

1. 트리형태의 입력값을 저장하기 위한 배열 arr을 선언하고 엣지정보를 각 노드에 저장한다.

2. 각 노드의 방문 여부와 거리를 저장하는 visited를 선언한다.

   • 이때 visited의 모든 값은 -1로 초기화해준다.

3. 시작 지점 s를 기준으로 bfs를 수행한다.

   • visited의 각 노드 값이 -1이라면 방문을 하지 않은 것이므로 큐에 담아주고 visited의 해당 노드 위치에 현재 노드의 거리값 + 1을 저장해준다.
   • 이 과정을 큐가 비워질 때까지 반복한다.

4. 거리가 k인 노드 정보를 저장하기 위해 새로운 배열 result를 선언해준다.

5. visited의 각 노드를 돌며 노드의 값이 k인 값을 result에 저장한다.

6. 만약 결과 배열 result가 비어있다면 최단 거리가 k인 노드(도시)가 없다는 것이므로 -1을 출력하고
   아니라면 오름차순 정렬(문제에서 오름차순으로 출력하라고 했으므로)한 뒤 각 노드 번호를 출력해준다.