kingsubin

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int n, m, k, x;
    public static ArrayList<ArrayList<Integer>> graph
            = new ArrayList<ArrayList<Integer>>();

    // 모든 도시에 대한 최단 거리 초기화
    public static int[] d = new int[300001];

    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()); // 출발 도시의 번호

        // 그래프 및 최단 거리 테이블 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
            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);
        }

        // 출발 도시까지의 거리는 0으로 설정
        d[x] = 0;

        // BFS
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(x);

        while (!q.isEmpty()) {
            int now = q.poll();
            for (int i = 0; i < graph.get(now).size(); i++) {
                int nextNode = graph.get(now).get(i);

                if (d[nextNode] == -1) {
                    d[nextNode] = d[now] + 1;
                    q.offer(nextNode);
                }
            }
        }

        // 최단 거리가 K 인 모든 도시의 번호를 오름차순 출력
        boolean check = false;
        for (int i = 1; i <= n; i++) {
            if (d[i] == k) {
                System.out.println(i);
                check = true;
            }
        }

        // 최단거리인 K인 도시가 없으면 -1 출력 
        if (!check) {
            System.out.println(-1);
        }
    }
}

 

1. BFS 사용을 떠올린다.

2. 최단 거리가 K인 모든 도시들의 번호가 필요하다.

3. 입력받은 도시의 연결 정보 graph에 담는다.

4. 최대 30,000개의 도시가 가능, 모든 도시의 거리를 -1으로 초기화한다.

5. 출발 도시의 거리는 0으로 설정.

6. Queue 자료구조에 시작도시를 넣고 BFS를 수행한다.

7. Queue가 빌때까지 해당 도시에 연결된 도시에 방문한 적이 없으면 해당 도시에 현재 도시의 d에서 +1 시키고 다시 큐에 넣는다.

8. 위의 과정을 수행하면 d배열에 거리가 담기게 되고 배열에서 k값과 같은 도시를 오름차순으로 출력한다.

9. 만약에 존재하지않으면 -1출력

 

 

- bfs/dfs 이해가 잘 안된다 ....

- 이거 한 문제도 코드 보고 따라가는데도 어렵다 .

---

https://www.acmicpc.net/problem/18352