[BOJ/Gold 4] 백준 28333 화이트 칼라(C++)

문제 링크

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

28333번: 화이트 칼라

 

문제

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

오늘 아침, 이 정보를 입수한 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

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

1 3 4
1 2 3 5

 

알고리즘 분류

• 그래프 탐색

 

풀이

직원들을 배치하기 위해서 BFS 경로를 추적해야 하기 때문에, 1번 도시부터 BFS를 수행하며 각 도시마다 도달할 때까지 걸리는 최소 비용을 기록하면서, 각 도시마다 해당 도시에 도달하기 직전의 도시들의 번호를 기록한다.

이후 DFS로 N번 도시부터 시작해서 경로를 역추적하여 1번 도시로 도달할 때까지 닐 카프리가 방문할 수 있는 모든 도시를 기록한다.

마지막으로 닐 카프리가 방문할 수 있는 모든 도시를 공백으로 구분하여 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <algorithm>
#define MAX 1001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int T, N, M, A, B;
vector<int> Edge[MAX];
int Visited[MAX];
vector<int> Prev[MAX];
set<int> Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Edge[i].clear();
        Visited[i] = INF;
        Prev[i].clear();
    }
    Answer.clear();
}

void BFS() {
    queue<pair<int, int> > Q;
    Visited[1] = 0;
    Q.push(make_pair(1, 0));

    while (!Q.empty()) {
        int NowX = Q.front().first;
        int NowT = Q.front().second;
        Q.pop();

        for (int i = 0; i < (int)Edge[NowX].size(); i++) {
            int NextX = Edge[NowX][i];
            if (Visited[NextX] > NowT + 1) {
                Visited[NextX] = NowT + 1;
                Prev[NextX].push_back(NowX);
                Q.push(make_pair(NextX, NowT + 1));
            }
            else if (Visited[NextX] == NowT + 1) {
                Prev[NextX].push_back(NowX);
            }
        }
    };
}

void trace_Path(int NowX, int NowT) {
    Answer.insert(NowX);
    if (NowX == 1) {
        return;
    }

    for (int i = 0; i < (int)Prev[NowX].size(); i++) {
        int PrevX = Prev[NowX][i];
        if (Answer.find(PrevX) == Answer.end()) {
            trace_Path(PrevX, NowT - 1);
        }
    }
}

void settings() {
    BFS();
    trace_Path(N, Visited[N]);
}

void find_Answer() {
    for (auto IT : Answer) {
        cout << IT << " ";
    }
    cout << "\n";
}

void input() {
    cin >> T;
    while (T--) {
        init();
        cin >> N >> M;
        for (int i = 0; i < M; i++) {
            cin >> A >> B;
            Edge[A].push_back(B);
        }
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}