백준 온라인 저지, DFS / 25195번: Yes or yes (파이썬 / 백준 골드문제)

문제 주소: https://www.acmicpc.net/problem/25195

문제

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

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

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

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

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

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

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

입력

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

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

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

이후 $M+3$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 $s$ 가 차례대로 $S$개 만큼 주어진다. ($1 \le s \le 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 \rightarrow 2 \rightarrow 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를 통해 곰곰이를 만나는지 만나지 못하는지 체크하여 출력한다.
- 해당 문제에는 사이클이 없기에 곰곰이의 위치에는 방문처리를 해 문제를 해결한다.

코드

# https://www.acmicpc.net/problem/25195
# 접근 방법
# DFS를 통해 곰곰이를 만나는지 만나지 못하는지 체크하여 출력한다.
# 해당 문제에는 사이클이 없기에 곰곰이의 위치에는 방문처리를 해 문제를 해결한다.
def dfs(s):
    visited[s] = True
    is_meet = not bool(graph[s])
    for u in graph[s]:
        if not visited[u] and dfs(u):
            return True
    return is_meet

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
visited = [False for _ in range(n+1)]
s = int(input())
for x in list(map(int, input().split())):
    visited[x] = True
print("Yes" if visited[1] or not dfs(1) else "yes")