(BOJ) 14615 Defend the CTP!!!

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

 

문제풀이: 

1번 부터 bfs 돌려서 갈 수 있는 곳들 찾아 놓음

진행 방향을 반대로 바꿔서 n번 부터 bfs 돌려서 갈 수 있는 곳들 찾아 놓기

폭탄 설치될 때 1에서 그 곳 갈 수 있고, (진행 방향 반대일 때) n번에서도 갈 수 있는 곳이면 "defend the CTP"

아니면 "Destroyed the CTP"

 

소스코드:

int n, m, tc;
bool visit[100001],cango[100001];

vector<vector<int>> v,v2;
queue<int> q;

bool bfs() {
	memset(visit, false, sizeof(visit));
	while (!q.empty()) q.pop();
	visit[n] = true;
	q.push(n);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int i : v2[cur]) {
			if (visit[i]) continue;
			visit[i]=true;
			q.push(i);
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;

	v.resize(n + 1);
	v2.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int q, w;
		cin >> q >> w;
		v[q].push_back(w);
		v2[w].push_back(q);
	}
	q.push(1);
	cango[1] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int i : v[cur]) {
			if (cango[i]) continue;
			cango[i] = true;
			q.push(i);
		}
	}
	bfs();
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		int q;
		cin >> q;
		if(!cango[q] || !visit[q]) cout << "Destroyed the CTP\n";
		else cout << "Defend the CTP\n";
	}

	
	return 0;
}