문제 탐색하기

입력 자료 정리

1. n은 노드의 개수, m은 간선의 개수, k는 최단거리로 검증에 활용되는 입력이며,
   x는 탐색을 시작할 노드의 번호다
2. 이후 들어오는 m개의 간선은 첫번째 노드 번호에서 두번째 노드 번호로 가는
   단방향 간선이다

해결방법 추론

1. 가중치가 1이라는 것에 주목하여 해결방법을 생각하였다
2. 가중치가 다르다면 다익스트라로 풀어야겠다는 생각을 하겠지만, 1이기 때문에
   BFS로도 손쉽게 풀 수 있을 것이라 생각하였다
3. BFS 탐색을 하면서 큐에 넣을 때, 기존 누적된 탐색 거리에 1을 더한 뒤
   큐에서 꺼냈을 때 k랑 같다면 정답 리스트에 넣고 나중에 한번에 꺼내서 출력한다면
   문제를 해결할 수 있을 것이다

시간복잡도 계산

1. BFS는 x와 연결된 노드의 개수만큼 진행된다.
2. 이때 m개의 간선이 모두 x와 연결되는 경우가 최악의 경우이므로,
   시간복잡도는 O(m)이 될 것이다.
3. 따라서 m의 최대 입력값은 백만 이므로, 시간 제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n,m,k,x는 변수로 관리하며, 이후 들어오는 간선은 리스트 배열로 관리한다
2. 저번 문제와 마찬가지로 리스트 배열을 선언한다.
   이번에는 단방향으로만 연결하면 되기 때문에 a인덱스에 b를 추가한다

BFS 탐색 설계

1. BFS 탐색을 위한 방문배열과 정답을 담을 리스트를 하나씩 선언해두고 BFS 탐색을 시작한다
2. BFS 탐색에서 큐에 넣을 값은 두개다. 따라서 int형 배열을 큐의 타입으로 선언한다
3. 0번 인덱스는 현재 노드 번호를 관리하며, 1번 인덱스는 이동한 최단 누적 거리를 말한다
4. x로 시작하기 때문에 x의 누적 거리는 0이며, 이 값을 큐에 넣고 시작한다
5. 큐가 빌때까지 BFS 탐색을 한다. 이때 만약 1번 인덱스의 값이 k랑 같다면
   0번 인덱스의 값은 ans 리스트에 넣어준다
6. 현재 번호에 해당하는 리스트 배열의 인덱스에 연결된 모든 값들을 탐색하여
   미방문했다면 방문체크하고 큐에 넣어준다. 이때 누적 거리는 1 증가한다

출력 설계

1. BFS 탐색을 통해 완성한 리스트가 비어있다면 -1을 출력하고,
   아니라면 리스트에 있는 모든 값을 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공!)

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


public class Main {

    static List<Integer>[] lists;
    static boolean[] visited;
    static List<Integer> ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
        lists = new ArrayList[n+1];
        for (int i = 0; i < n + 1; i++) {
            lists[i] = new ArrayList<>();
        }
        visited = new boolean[n+1];
        ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lists[a].add(b);
        }
        bfs(x,k);

        if(ans.isEmpty()){
            bw.write("-1");
        }else{
            Collections.sort(ans);
            for (Integer an : ans) {
                bw.write(an+"\n");
            }
        }

        br.close();
        bw.close();
    }

    private static void bfs(int x, int k) {
        Queue<int[]> q = new LinkedList<>();
        visited[x] = true;
        q.add(new int[]{x, 0});
        while(!q.isEmpty()) {
            int[] tmp = q.poll();
            if(tmp[1] == k){
                ans.add(tmp[0]);
            }

            for (Integer i : lists[tmp[0]]) {
                if(!visited[i]){
                    visited[i] = true;
                    q.add(new int[]{i, tmp[1] + 1});
                }
            }
        }


    }
}

문제 링크

18352번 - 특정 거리의 도시 찾기