[백준] 25195 Yes or yes

문제

 $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 를 출력한다.

내 풀이

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    
s = int(input())

fan = list(map(int, input().split()))

visited_bfs = [0]*(n+1)
visited_dfs = [0]*(n+1)

# with recursive func
def DFS(graph, start, visited_dfs):
    visited_dfs[start] = 1
    
    for i in graph[start]:
        if visited_dfs[i] == 0:
            DFS(graph, i, visited_dfs)    

# with deque
def BFS(graph, start, visited_bfs):    
    q = deque([start])
    visited_dfs[start] = 1
    
    while q:
        now = q.popleft()
        for i in graph[now]:
            if visited_bfs[i] == 0:
                visited_bfs[i] = 1
                q.append(i)
    
DFS(graph, 1, visited_bfs)
BFS(graph, 1, visited_dfs)

result1 = [i for i,v in enumerate(visited_bfs) if v!=0]
result2 = [i for i,v in enumerate(visited_dfs) if v!=0]

result11 = list(set(result1) & set(fan))
result22 = list(set(result2) & set(fan))

if len(result11)==0 and len(result22)==0:
    print('yes')
else:
    print('Yes')

나는 이 문제를 BFS와 DFS를 모두 이용하여 탐색했을 때 팬클럽을 만나지 않는 경우의 수가 생기는지를 확인하는 방식으로 풀었다. 그러나 오답이었고 다른 풀이를 참고하여 다시 풀어서 정답을 받은 코드가 아래 코드이다. (설명은 코멘트 참조)

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    
s = int(input())

fan = list(map(int, input().split()))

visited = [0]*(n+1)

# 팬클럽 곰곰이가 있는 노드는 방문 처리
for i in fan:
    visited[i] = 1
    
def BFS(graph, start):
    q = deque([start])
    if visited[start]:
        return 'Yes'
    visited[start] = 1
    while q:
        now = q.popleft()
        if not graph[now]:
            return 'yes'
        for i in graph[now]:
            if not visited[i]:
                visited[i] = 1
                q.append(i)
    return 'Yes'

print(BFS(graph, 1))

코멘트

산만한 문제를 정말 싫어하는데...투어리스트랑 팬클럽 이름도 똑같이 만들고 프린트하는 것도 "Yes"랑 "yes"로 헷갈리게 해놔서 너무 정신없고 처음부터 풀기 싫어졌다...
확실한 것은 이번 문제는 DFS와 BFS를 모두 사용해야 하는 것이 아니라 둘 중 하나만 이용해도 된다는 것이다. 왜냐하면 이 문제는 방문의 순서가 달라지는 것이 아니라 방문하는 모든 루트에서 팬클럽을 만나느냐 마느냐의 문제이기 때문이다. 실제로 reference 달아놓은 두 풀이가 각각 DFS, BFS를 이용하여 풀었다. 이 문제에서 중요한 것은 팬클럽이 있는 노드를 방문하지 않도록 해서 끝까지 (리프 노드) 에 도달할 수 있는지를 보는 것이다.
그래서 팬클럽이 있는 노드를 미리 방문처리 (visited[i] = 1) 하고 리프 노드에 도달하면 'yes', 그렇지 않다면 'Yes'를 출력하도록 하면 된다.
아이디어는 이해가 되었는데 사실 BFS 함수가 잘 이해가 되지 않는다. 왜 초반부부터 if visited[start]: return 'Yes'로 체크를 하는지도 이해가 잘 되지 않고 맨 마지막에 return 'Yes'가 있으면 앞에 어떤 과정이 있더라도 결국은 'Yes'가 출력되는 것 아닌가? 하는 의문이 든다.

References

https://www.acmicpc.net/problem/25195
https://ymg5218.tistory.com/142
https://velog.io/@xx0hn/BOJ-Python-25195번-Yes-or-yes