[BOJ/백준] 28333 - 화이트 칼라

28333번: 화이트 칼라

---

BFS + BFS

---

---

• 제목

화이트 칼라

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다.

오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 검거하기 위한 작전을 세우고 있다. AdbyMe, Inc. 는 그가 현재 어느 도시에 있는지, 그리고 뮤직박스가 어느 도시에 있는지 파악했고, 그를 잡기 위해 직원들을 배치할 것이다. AdbyMe, Inc. 가 입수한 정보에 의하면 닐 카프리는 매우 급한 성격 (?)이고, 그의 성격으로 볼 때, 현재 위치에서 뮤직박스가 있는 곳까지 최단 경로로 이동할 것이다.

그래서 AdbyMe, Inc. 는 현재 닐 카프리가 있는 도시와 뮤직박스가 있는 도시, 그리고 그가 이동할 때 거쳐갈 가능성이 있는 모든 도시에 직원들을 배치하려고 한다. 지도를 보고 직원들을 배치해야 되는 도시를 모두 골라내자.

---

• 입력

입력은 T개의 테스트 케이스로 구성된다. 입력의 첫 행에는 T가 주어진다.

각 테스트 케이스의 첫 행에는 도시의 수 N (2 ≤ N ≤ 1,000), 도시 간에 연결된 길의 수 M (1 ≤ M ≤ 50,000)이 주어진다. 그 다음 M행에 연결된 도시의 번호 Ai와 Bi가 주어진다. 모든 길은 그 길이가 같은 Ai에서 Bi로 이동하는 일방통행 길이다. (1 ≤ Ai , Bi ≤ N, Ai ≠ Bi)

닐 카프리는 현재 1번 도시에 위치해 있고, 뮤직박스는 N번 도시에 위치해 있다. 1번 도시에서 N번 도시로 이동 가능한 경로는 반드시 하나 이상 존재한다.

---

• 출력

각 테스트 케이스에 대해 한 행에 하나씩 AdbyMe, Inc. 가 직원들을 배치해야하는 도시의 번호를 오름차순으로 출력한다.

---

예제 입력1	예제 출력1
2 4 5 1 2 2 1 1 3 3 4 4 3 5 6 1 2 1 3 2 5 3 4 3 5 4 5	1 3 4 1 2 3 5

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    public static void main(String[] args) throws Exception {
        Queue<Integer> queue;
        HashSet<Integer> answer;
        HashMap<Integer, ArrayList<Integer>> front, back;
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int[] dist = new int[N + 1];
            Arrays.fill(dist, Integer.MAX_VALUE);

            front = new HashMap<Integer, ArrayList<Integer>>();
            back = new HashMap<Integer, ArrayList<Integer>>();

            for(int i = 0; i < M; i++){
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                if(!front.containsKey(from)) front.put(from, new ArrayList<Integer>());
                front.get(from).add(to);
                if(!back.containsKey(to)) back.put(to, new ArrayList<Integer>());
                back.get(to).add(from);
            }

            queue = new ArrayDeque<Integer>();
            queue.add(1);
            dist[1] = 0;
            while(!queue.isEmpty()){
                int curr = queue.poll();
                if(front.containsKey(curr)){
                    for(int next : front.get(curr)){
                        if(dist[next] > dist[curr] + 1){
                            dist[next] = dist[curr] + 1;
                            queue.add(next);
                        }
                    }
                }
            }

            queue = new ArrayDeque<Integer>();
            queue.add(N);
            while(!queue.isEmpty()){
                int curr = queue.poll();
                if(back.containsKey(curr)){
                    for(int next : back.get(curr)){
                        if(dist[next] == -1) continue;
                        if(dist[curr] - 1 == dist[next]){
                            queue.add(next);
                        }
                    }
                }
                dist[curr] = -1;
            }
            for(int i = 1; i <= N; i++) if(dist[i] == -1) sb.append(i).append(" ");
            sb.append('\n');
        }
        System.out.println(sb);
    }
}