[BOJ/Gold 4] 백준 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" 를 출력하자.

입력

첫째 줄에는 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000)

이후 M줄에 걸쳐서 간선의 정보를 나타내는 두 정수 u, v가 주어진다. 이는 정점 u에서 정점 v로 가는 간선이 있음을 의미한다. (1 ≤ u, v ≤ N, u ≠ v)

이후 M + 2번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수 S가 주어진다. (1 ≤ S ≤ N)

이후 M + 3번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 s가 차례대로 S개 만큼 주어진다. (1 ≤ s ≤ N)

주어진 그래프는 사이클이 없음이 보장된다. 또한 두 정점을 연결하는 간선은 최대 한 개이다.

팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다.

출력

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

예제 입력 1

7 7
1 2
2 3
2 4
3 4
1 5
5 7
6 7
3
4 3 5

예제 출력 1

Yes

예제 입력 2

7 7
1 2
2 3
2 4
3 4
1 5
5 7
6 7
2
3 5

예제 출력 2

yes

 1 → 2 → 4경로를 따라 여행을 떠나면 팬클럽 곰곰이를 만나지 않고 여행을 할 수 있다.

예제 입력 3

2 1
1 2
1
1

예제 출력 3

Yes

출발지인 1번 노드에 팬클럽 곰곰이가 있으므로 투어리스트 곰곰이가 여행을 시작하자마자 팬클럽 곰곰이를 만나게 된다.

예제 입력 4

100000 1
4 3
5
3 4 5 6 100000

예제 출력 4

yes

알고리즘 분류

• 그래프 탐색

풀이

DFS를 통해 모든 노드를 탐색하면서, 경로의 끝까지 가기 전에 팬클럽을 만난 경우가 없다면 yes를 출력하고, 그게 아니라면 Yes를 출력한다.

여기서 1번 노드에 팬클럽이 있다면 무조건 Yes를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, U, V, S;
bool Fan[MAX];
vector<int> Edge[MAX];
int Answer;

void input() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> U >> V;
        Edge[U].push_back(V);
    }
    cin >> S;
    for (int i = 0; i < S; i++) {
        cin >> U;
        Fan[U] = true;
    }
}

void DFS(int Now, bool Flag) {
    if (Edge[Now].empty()) {
        if (Flag) {
            Answer = true;
        }
        return;
    }

    for (int i = 0; i < Edge[Now].size(); i++) {
        int Next = Edge[Now][i];
        if (Fan[Next]) {
            DFS(Next, false);
        }
        else {
            DFS(Next, Flag);
        }
    }
}

void settings() {
    DFS(1, true);
    if (Fan[1]) {
        Answer = false;
    }
}

void find_Answer() {
    if (Answer) {
        cout << "yes\n";
    }
    else {
        cout << "Yes\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}