백준 알고리즘 14615번 : Defend the CTP!!!

링크

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

fail1) BFS 시간초과

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/rope>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using namespace __gnu_cxx;

#define X first
#define Y second
#define int int64_t
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define Compress(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define OOB(x, y) ((x) < 0 || (x) >= n || (y) < 0 || (y) >= m)
#define IDX(v, x) (lower_bound(all(v), x) - (v).begin())
#define debug(x) cout << (#x) << ": " << (x) << '\n'

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tii = tuple<int, int, int>;
template <typename T>
using wector = vector<vector<T>>;

vector<int> dist(100001, -1);
vector<int> adj[100001];
int n,m,t;
void bfs(int st,int x){
	dist[st] = 1;
	queue<int> Q;
	Q.push(st);
	while(!Q.empty()){
		auto cur = Q.front(); Q.pop(); 
		if(cur == x) break;
		for(auto nxt : adj[cur]){
			if(nxt < 1 || nxt > n) continue;
			dist[nxt] = dist[cur] + 1;
			Q.push(nxt);
		}
	}			
};

int32_t main(){
	fastio;
	cin >> n >> m;
	while(m--){
		int a,b; cin >> a >> b;
		adj[a].push_back(b);
	}
	cin >> t;
	while(t--){
		fill(all(dist), -1);
		int x; cin >> x;		
		bfs(1, x);
		bfs(x, n);
		dist[n] == -1 ? cout << "Destroyed the CTP\n" : cout << "Defend the CTP\n";
	}
}

그냥 단순하게 x의 좌표를 거쳐서 가야하니 1->x 에서 bfs한번
x -> n으로 bfs를 돌려서 도달했는지 체크를 했지만 정점이 10만개이기 때문에 TLE가 뜰 수밖에 없었습니다.

sol1) 정방향 BFS,역방향 BFS

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/rope>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using namespace __gnu_cxx;

#define X first
#define Y second
#define int int64_t
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define Compress(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define OOB(x, y) ((x) < 0 || (x) >= n || (y) < 0 || (y) >= m)
#define IDX(v, x) (lower_bound(all(v), x) - (v).begin())
#define debug(x) cout << (#x) << ": " << (x) << '\n'

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tii = tuple<int, int, int>;
template <typename T>
using wector = vector<vector<T>>;

vector<int> adj[100001],adj2[100001];
int n,m,t; 

int32_t main(){
	fastio;
	cin >> n >> m;
	vector<bool> vist1(n + 1,false),vist2(n + 1, false);
	while(m--){
		int a,b; cin >> a >> b;
		adj[a].push_back(b);
		adj2[b].push_back(a);
	}
	// 1 -> n bfs
	queue<int> Q;
	vist1[1] = true;
	Q.push(1);
	while(!Q.empty()){
		auto cur = Q.front(); Q.pop();
		for(auto nxt : adj[cur]){
			if(nxt < 1 || nxt > n || vist1[nxt]) continue;
			vist1[nxt] = true;
			Q.push(nxt);
		}
	}
	// n -> 1 bfs
	queue<int> Q1;
	vist2[n] = true;
	Q1.push(n);
	while(!Q1.empty()){
		auto cur = Q1.front(); Q1.pop();
		for(auto nxt : adj2[cur]){
			if(nxt < 1 || nxt > n || vist2[nxt]) continue;
			vist2[nxt] = true;
			Q1.push(nxt);
		}
	}
	// query
	cin >> t;
	while(t--){
		int x; cin >> x;		
		cout << ((vist1[x] && vist2[x]) ? "Defend the CTP\n" : "Destroyed the CTP\n");
	}
}

그래프의 간선이 단방향이기 때문에 그래프를 2개를 구성해주면 됩니다.
adj에는 1 -> n 그래프의간선을, adj2에는 n -> 1의 그래프의 간선을 저장후 bfs를 2번 돌려서 x에 도달가능한 지를 미리 구해주면 들어오는 쿼리를 O(1)에 처리해줄 수 있습니다.