[BOJ/Gold 4] 백준 14615 Defend the CTP!!!(C++)

문제 링크

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

14615번: Defend the CTP!!!

 

문제

지금으로부터 527년이 지난 서기 2544년, 항성 간 이동이 가능해진 인류는 태양계가 아닌 새로운 보금자리를 찾아 기술의 집약체인 CTP(Cho Technology Planet, 초 기술 행성)를 건설한다. 인공지능이 관리하는 CTP 안에서는 자연재해도 전쟁도 없었으며 많은 사람이 행복을 누리며 살아나갔다.

CTP에는 N개의 도시가 있는데 각각의 도시들은 1번부터 N번까지 고유한 번호를 가지고 있으며 각 도시들끼리는 매우 빠른 속도로 이동할 수 있는 튜브로 연결되어 있다. 단 튜브는 매우 빠른 속도로 이동해야 하기 때문에 한 방향으로만 이동을 할 수 있다. 즉 A도시에서 B도시로 이동하는 튜브가 있다고 해서 B도시에서 A도시로 이동하는 튜브가 항상 존재하는 것은 아니다. 또한 튜브 안에서는 매우 빠른 속도로 이동이 가능하기 때문에 두 도시가 아무리 멀리 떨어져 있어도 이동하는 시간은 무시할만큼 적게 든다.

모든 사람들의 유토피아 CTP는 어느 날 우주급 빌런 재유니스의 침공으로 건설 이래 최대 위기에 직면한다. 재유니스는 N개의 도시 중 한 도시에 CTP를 한 번에 파괴할 수 있는 위력의 반물질 폭탄을 설치하고 사라진다. CTP를 구하기 위해서는 반물질 폭탄을 N번 도시에 있는 항성 간 이동장치를 통해 블랙홀로 보내야 한다. 가장 이상적인 방법은 반물질 폭탄이 있는 도시에서 폭탄을 N번 도시로 보내면 되지만 폭탄은 일반 사람이 들기에 너무 무겁기에 1번 도시에 있는 슈퍼히어로 미노만이 들고 이동할 수 있다.

튜브의 이동속도는 매우 빠르기 때문에 미노가 1번 도시에서 반물질 폭탄이 있는 도시로 이동한 다음에 폭탄을 들고 다시 N번 도시로 이동할 수만 있다면 CTP를 구할 수 있다. 이동하는 과정에서 똑같은 튜브를 다시 사용할 수 있고 방문했던 도시를 또다시 방문할 수도 있다. 또한 이동경로의 길이 제한은 없다.

과연 슈퍼히어로 미노는 위기에 빠진 CTP를 구할 수 있을까? 입력으로는 T개의 시나리오가 주어진다. 시나리오마다 재유니스가 반물질 폭탄을 설치한 도시의 번호가 주어진다. 각각의 시나리오에 대해 슈퍼히어로 미노가 CTP를 지킬 수 있는지 알아보는 프로그램을 작성하자.

 

입력

첫 번째 줄에 N(3 ≤ N ≤ 100,000)과 M(1 ≤ M ≤ 1,000,000)이 주어진다.

N은 CTP에 존재하는 도시의 개수를 의미하고 M은 CTP에 존재하는 튜브의 개수를 의미한다.

다음 M개의 줄에 걸쳐 X, Y(1 ≤ X, Y ≤ N)가 주어지는데 X에서 Y로 이동할 수 있는 튜브가 있다는 뜻이다.

다음 줄에는 시나리오의 개수 T(1 ≤ T ≤ 100,000)가 주어진다.

다음 T개의 줄에 차례대로 C(2 ≤ C ≤ N-1)가 주어지는데 이는 우주급 빌런 재유니스가 반물질 폭탄을 설치한 도시의 번호를 의미한다.

 

입/출력의 양이 많으므로 속도가 빠른 입/출력 함수를 사용하는것을 권장한다.

 

출력

T개의 줄에 걸쳐 CTP를 지킬 수 있는지 결과를 출력한다.

만약 CTP를 구할 방법이 없다면 “Destroyed the CTP”를 출력하고 슈퍼히어로 미노가 CTP를 구할 수 있다면 “Defend the CTP”를 출력한다. 모든 출력은 쌍따옴표를 제외하고 출력한다.

 

예제 입력 1

6 8
1 3
5 4
3 5
4 6
1 2
3 2
3 4
4 2
3
5
4
2

예제 출력 1

Defend the CTP
Defend the CTP
Destroyed the CTP

 

힌트

아래 그림은 N이 6인 CTP의 서로 다른 두 시나리오를 보여준다.

 

그림 (a)는 5번 도시에 반물질 폭탄이 설치된 시나리오다. 슈퍼히어로 미노는 1번 도시에서 빨간색으로 표시된 튜브를 따라 5번 도시로 이동한 뒤 폭탄을 가지고 6번 도시로 이동하면 CTP를 구할 수 있다. 그림 (b)는 2번 도시에 반물질 폭탄이 설치된 경우다. 이 경우는 빨간색으로 표시된 튜브를 따라 2번 도시로 이동할 수 있지만 2번 도시에서 6번 도시로 이동할 수 없기 때문에 CTP는 빌런 재유니스에 의해 파괴된다.

 

알고리즘 분류

• 그래프 탐색

 

풀이

간선은 단방향이기 때문에 역방향 간선을 위한 배열을 하나 더 선언한다.

T개의 도시에 반물질 폭탄을 설치했다고 가정하고 BFS를 수행한다면 BFS를 총 100,000번 수행해야 하므로 시간 초과가 발생한다.

따라서 BFS를 1번 수행함으로써 1번 도시에서 C번 도시까지, 혹은 C번 도시에서 N번 도시까지 이동할 수 있는지를 판별하기 위한 방문 여부를 기록한다.

Boolean 타입을 추가함으로써 역방향 간선을 탐색해야 하는지, 아니면 정방향 간선을 탐색해야 하는지를 나타낼 수 있다.

마지막으로 T개의 도시를 입력받으며 1번 도시에서 정방향 간선을 통해 C번 도시를 방문했는지의 여부와 N번 도시에서 역방향 간선을 통해 C번 도시를 방문했는지의 여부를 파악한다.

둘 다 true면 CTP를 구할 수 있고 그게 아니라면 CTP는 빌런 재유니스에 의해 파괴된다.

 

코드

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

using namespace std;
int N, M, T, X, Y, C;
vector<int> Edge[MAX];
vector<int> reverse_Edge[MAX];
bool Visited[2][MAX];

void bfs() {
    queue<pair<int, bool> > Q;
    Visited[0][1] = true;
    Visited[1][N] = true;
    Q.push(make_pair(1, false));
    Q.push(make_pair(N, true));

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

        if (isReversed) {
            for (int i = 0; i < (int)reverse_Edge[NowX].size(); i++) {
                int NextX = reverse_Edge[NowX][i];
                if (!Visited[isReversed][NextX]) {
                    Visited[isReversed][NextX] = true;
                    Q.push(make_pair(NextX, isReversed));
                }
            }
        }
        else {
            for (int i = 0; i < (int)Edge[NowX].size(); i++) {
                int NextX = Edge[NowX][i];
                if (!Visited[isReversed][NextX]) {
                    Visited[isReversed][NextX] = true;
                    Q.push(make_pair(NextX, isReversed));
                }
            }
        }
    };
}

void settings() {
    bfs();
}

void find_Answer() {
    if (Visited[0][C] && Visited[1][C]) {
        cout << "Defend the CTP\n";
    }
    else {
        cout << "Destroyed the CTP\n";
    }
}

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

int main() {
    FASTIO
    input();

    return 0;
}