백준 25195 Yes or yes C++

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

25195번: Yes or yes

---

문제

 N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.

투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.

투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.

오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.

조금 쉽게 말하자면 넌 뭘 골라도 날 만나게 될 거야 Twice, YES or YES 가사 중 일부

투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.

투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.

---

---

출력

문제에서 설명한 조건에 맞춰서 Yes 또는 yes 를 출력한다.

---

간선을 따라서 이동할 수 없는 경우 -> graph[]의 크기가 0인 경우인데,

이 경우 그래프 탐색을 통해 방문을 했다면 팬을 만나지 않고 방문한 경우이다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

int has_pan[100001];
vector<int> graph[100001];
int n,m;
int k;

void input(){
	cin >> n >> m;
	for(int i = 0;i<m;i++){
		int A,B;
		cin >> A >> B;
		graph[A].push_back(B);
	}
	cin >> k;
	for(int i = 0;i<k;i++){
		int x;
		cin >> x;
		has_pan[x] = 2; //팬을 만나는 경우 -> has_pan[정점] = 2
	}
}

void bfs(int start){
    if(has_pan[start] == 2){
        return;
    }
	queue<int> q;
	q.push(start);
	has_pan[start] = 1;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		for(int i = 0;i<graph[cur].size();i++){
			int y = graph[cur][i];
			if(has_pan[y] == 0){
				has_pan[y] = 1;
				q.push(y);
			}
		}
	}
} 
int main(void){
	input();
	bfs(1);
	bool flag = false;
	for(int i = 1;i<=n;i++){
        //이동할 수 없는 정점이고 팬을 만나지 않았다면
		if(graph[i].size() == 0 && has_pan[i] == 1){
			flag = true;
		}
	}
	if(flag == true){
		cout << "yes";
		return 0;
	}
	cout << "Yes";
}