[ BOJ / C++ ] 25195번 : Yes or yes
[ BOJ ] 25195번 : Yes or yes
문제 : https://www.acmicpc.net/problem/25195
[ 문제 ]
개의 정점과 개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.
투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.
투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.
오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.
조금 쉽게 말하자면
넌 뭘 골라도 날 만나게 될 거야
Twice, YES or YES 가사 중 일부
투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.
투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.
[ 입력 ]
첫째 줄에는 정점의 개수 과 간선의 개수 이 주어진다. ()
이후 줄에 걸쳐서 간선의 정보를 나타내는 두 정수 u, v 가 주어진다. 이는 정점 에서 정점 로 가는 간선이 있음을 의미한다. (, , )
이후 번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수 가 주어진다. ()
이후 번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 가 차례대로 개 만큼 주어진다. ()
주어진 그래프는 사이클이 없음이 보장된다. 또한 두 정점을 연결하는 간선은 최대 한 개이다.
팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다.
[ 출력 ]
문제에서 설명한 조건에 맞춰서 Yes 또는 yes 를 출력한다.
[ 문제 접근 및 풀이 ]
팬클럽 곰곰이를 만나지 않고 이동하는 방법은
루트에서 리프노드까지 팬클럽 곰곰이가 없는 길이다.
따라서 팬클럽 곰곰이를 가지 못하는 정점이라고 생각하고
BFS를 통해서 정점까지 가게 된다면 yes를
정점을 가지 못 한다면 Yes를 출력해주었다.
[ 소스 코드 ]
#include<bits/stdc++.h>
using namespace std;
int N,M,u,v,S,s;
vector<int> V[100001];
bool gomgom[100001],vis[100001];
void Q_25195();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Q_25195();
}
void Q_25195(){
cin >> N >> M;
for(int i=0;i<M;i++){
cin >> u >> v;
V[u].push_back(v);
}
cin >> S;
for(int i=0;i<S;i++){
cin >> s;
gomgom[s]=true;
}
if(gomgom[1]) {
cout <<"Yes";
return;
}
queue<int> q;
vis[1]=true;
q.push(1);
while(!q.empty()){
auto cur=q.front(); q.pop();
if(V[cur].empty()){
cout << "yes";
return;
}
for(auto x:V[cur]){
if(gomgom[x] || vis[x]) continue;
vis[x]=true;
q.push(x);
}
}
cout<<"Yes";
}