BOJ 17220 :마약수사대

#BOJ 17220 :마약수사대

17220번: 마약수사대

#풀이

맨 처음에 보고 다익스트라를 생각했다가 문제를 다시 읽어보니 루트가 여러 개도 가능해서 그냥 bfs로 풀었다.

 

경찰이 잡은 마약범들은 인접리스트에서 지우고 루트에서 bfs를 돌린다.

 

그 이후 루트 빼고 방문한 정점의 개수를 구해야 하는데 마약범 인접리스트를 지워도 잡힌 마약범들은 방문할 수 도 있다.

 

그래서 마지막에 잡힌 마약범 방문표시를 제거해야 한다,

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n, m;
vector<int> adj[27];
bool Root[27];
int vis[27];
int toInt = 'A' - 1;
int root;

void bfs(int r){
	queue<int>q;
	q.push(r);
	
	while(!q.empty()){
		int cur = q.front();q.pop();
		
		for(auto nxt : adj[cur]){
			if(vis[nxt] != 0) continue;
			vis[nxt] = 1;
			q.push(nxt);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
		
	for(int i = 0; i <m; i++){
		char a,b;
		cin >> a >> b;
		adj[a - toInt].push_back(b - toInt);
		Root[b-toInt] = 1;
	}
	int k = 0;
	cin >> k;
	vector<int> del;
	for(int i = 0; i < k; i++){
		char h;
		cin >> h;
		adj[h-toInt].clear();
		del.push_back(h-toInt);
	}
	for(int i = 1; i <= n; i++){
		if(Root[i] == 0){
			root = i;
			vis[i] = 2;
			bfs(i);
		}
	}
	
	
	int ans = 0;
	for(auto de : del){
		vis[de] = 0;		
	}
	for(int i = 1; i <=n; i++){
		if(vis[i] == 1)
			ans++;
	}
	cout << ans << '\n';
	return 0;
}