[백준 25195] Yes or yes

문제

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

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

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

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

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

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

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

입력

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

이후 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번 노드에서 시작해서 더이상 길이 나오지 않을 때까지 전진하면 된다.

전형적인 DFS문제..근데 이제 곰곰이를 곁들인..

 

쉽게 생각해서 방문했던 노드는 재방문하지 않기 위한 조건 + 다음 방문하는 노드에 곰곰이가 있는지 check 하면 될 것 같다

다시 말해, dfs로 탐색하는 과정에서 다음 노드로 전진하는 조건이 (아직 방문 안한 노드 & 곰곰이가 없는 노드) 로 하면 된다

 

# 입력부
# 인접리스트 및 방문체크, 곰곰이 저장 변수 선언
N, M = map(int, input().split())
R = [[] for _ in range(N+1)]
visited = [True]*(N+1)
ans = "Yes"
for _ in range(M):
    u,v = map(int, input().split())
    R[u].append(v)
S = int(input())
arr_s = list(map(int,input().split()))

 

def dfs(node):
    visited[node] = False
    if len(R[node])==0:
        global ans
        ans = "yes"
        return
    for next_node in R[node]:
        if visited[next_node] and next_node not in arr_s:   # 아직 방문 안했고, 곰곰이 없으면 go
            dfs(next_node)

 

dfs(1)

# 시작 노드에서 곰곰이 만나면..
if 1 in arr_s:
    ans = "Yes"

print(ans)