# [Gold IV] Defend the CTP!!! [문제 링크](https://www.acmicpc.net/problem/14615) ## 문제 설명 <p dir="ltr">지금으로부터 527년이 지난 서기 2544년, 항성 간 이동이 가능해진 인류는 태양계가 아닌 새로운 보금자리를 찾아 기술의 집약체인 CTP(Cho Technology Planet, 초 기술 행성)를 건설한다. 인공지능이 관리하는 CTP 안에서는 자연재해도 전쟁도 없었으며 많은 사람이 행복을 누리며 살아나갔다.</p> <p dir="ltr">CTP에는 N개의 도시가 있는데 각각의 도시들은 1번부터 N번까지 고유한 번호를 가지고 있으며 각 도시들끼리는 매우 빠른 속도로 이동할 수 있는 튜브로 연결되어 있다. 단 튜브는 매우 빠른 속도로 이동해야 하기 때문에 한 방향으로만 이동을 할 수 있다. 즉 A도시에서 B도시로 이동하는 튜브가 있다고 해서 B도시에서 A도시로 이동하는 튜브가 항상 존재하는 것은 아니다. 또한 튜브 안에서는 매우 빠른 속도로 이동이 가능하기 때문에 두 도시가 아무리 멀리 떨어져 있어도 이동하는 시간은 무시할만큼 적게 든다.</p> <p dir="ltr">모든 사람들의 유토피아 CTP는 어느 날 우주급 빌런 재유니스의 침공으로 건설 이래 최대 위기에 직면한다. 재유니스는 N개의 도시 중 한 도시에 CTP를 한 번에 파괴할 수 있는 위력의 반물질 폭탄을 설치하고 사라진다. CTP를 구하기 위해서는 반물질 폭탄을 N번 도시에 있는 항성 간 이동장치를 통해 블랙홀로 보내야 한다. 가장 이상적인 방법은 반물질 폭탄이 있는 도시에서 폭탄을 N번 도시로 보내면 되지만 폭탄은 일반 사람이 들기에 너무 무겁기에 1번 도시에 있는 슈퍼히어로 미노만이 들고 이동할 수 있다.</p> <p dir="ltr">튜브의 이동속도는 매우 빠르기 때문에 미노가 1번 도시에서 반물질 폭탄이 있는 도시로 이동한 다음에 폭탄을 들고 다시 N번 도시로 이동할 수만 있다면 CTP를 구할 수 있다. 이동하는 과정에서 똑같은 튜브를 다시 사용할 수 있고 방문했던 도시를 또다시 방문할 수도 있다. 또한 이동경로의 길이 제한은 없다.</p> <p>과연 슈퍼히어로 미노는 위기에 빠진 CTP를 구할 수 있을까? 입력으로는 T개의 시나리오가 주어진다. 시나리오마다 재유니스가 반물질 폭탄을 설치한 도시의 번호가 주어진다. 각각의 시나리오에 대해 슈퍼히어로 미노가 CTP를 지킬 수 있는지 알아보는 프로그램을 작성하자.</p> ## 입력 <p>첫 번째 줄에 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)가 주어지는데 이는 우주급 빌런 재유니스가 반물질 폭탄을 설치한 도시의 번호를 의미한다. 입/출력의 양이 많으므로 속도가 빠른 입/출력 함수를 사용하는것을 권장한다.</p> ## 출력 <p>T개의 줄에 걸쳐 CTP를 지킬 수 있는지 결과를 출력한다. 만약 CTP를 구할 방법이 없다면 “Destroyed the CTP”를 출력하고 슈퍼히어로 미노가 CTP를 구할 수 있다면 “Defend the CTP”를 출력한다. 모든 출력은 쌍따옴표를 제외하고 출력한다.</p> ## 풀이 1부터 정방향 간선을 따라 도착할 수 있는 모든 정점을 기록하고, N부터 역방향 간선을 따라 도착할 수 있는 모든 정점을 기록을 하여 1 -> C -> N 이동이 가능한지 O(1)에 판단하였습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 100'001; int n, m; bool canGoFrom1[MAX], canGoToN[MAX]; vector<vector<int>> conn(MAX), inverseConn(MAX); void dfs1(int cur=1) { canGoFrom1[cur]=true; for(int next:conn[cur]) { if(!canGoFrom1[next]) dfs1(next); } } void dfs2(int cur=n) { canGoToN[cur]=true; for(int next:inverseConn[cur]) { if(!canGoToN[next]) dfs2(next); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; while(m--) { int x, y; cin >> x >> y; conn[x].push_back(y); inverseConn[y].push_back(x); } dfs1(); dfs2(); int t; cin >> t; while(t--) { int c; cin >> c; cout << (canGoFrom1[c] && canGoToN[c] ? "Defend the CTP\n" : "Destroyed the CTP\n"); } } ```