[파이썬/python] 백준 - 25195 Yes or yes

문제

https://www.acmicpc.net/problem/25195

---

문제 설명

1. N개의 정점과 M개의 간선으로 이루어진 DAG가 주어진다.
2. 곰곰이는 1번 정점부터 출발해 간선을 따라 이동한다. 더 이상 이동할 수 없는 경우 여행을 종료한다.
3. 곰곰이의 팬은 그래프 위의 정점 일부에서 잠복한다.
4. 곰곰이가 해당 정점을 지날 때 잠복한 팬이 존재한다면 서로 만나게된다.
5. 투어리스트 곰곰이가 어떻게 이동하더라도 팬을 만난다면 "Yes" 만나지 않고 여행할 수 있는 방법이 존재한다면 "yes"를 출력한다.

---

풀이

우선 그래프 탐색 문제이기 때문에 BFS 혹은 DFS로 접근했다.

 

BFS의 시간 복잡도는$O(V+E)$이다.

이 문제의 범위는 최악의 경우 $V = 10^5, E = 10^5$이므로 충분히 탐색이 가능하다고 판단했다.

 

다음으로 이동할 정점에 팬이 있다면 카운트를 늘려가면서 탐색을 진행했다.

 

이때 현재 정점을 기준으로 더 이상 탐색할 정점이 없다면, 지금까지 이동한 경로에서 팬을 만난 적이 있는지 확인한 뒤 팬을 만나지 않았다면 yes를 출력하도록 구현했다.

 

이 문제의 핵심 포인트는 문제에서 주어진 그래프의 형태가 DAG라는 점이다.

 

DAG는 Directed Acyclic Graph의 약자로, 방향성이 존재하고 사이클이 없는 그래프를 의미한다.

 

처음에는 문제에서 이 부분을 제대로 확인하지 않고 구현했다가 “틀렸습니다.”를 받았다.
원인은 방문 처리에 있었다.

 

일반적으로 그래프 탐색에서 방문 처리를 하는 이유는 그래프에 사이클이 존재할 경우 무한 루프가 발생할 수 있기 때문이다.

하지만 이 문제는 사이클이 존재하지 않는 DAG 구조이기 때문에 방문 처리를 하지 않아도 무한 루프가 발생하지 않는다.

 

오히려 방문 처리를 하게 되면 특정 경로를 탐색하지 못해 오답이 발생할 수 있다.

예를 들어 4번과 7번 정점에 팬클럽이 존재하는 그래프가 있다고 가정하자.

 

BFS를 진행하면 1 → 2 → 4 순서로 정점을 먼저 탐색하면서 4번 정점이 방문 처리된다.

 

이후 1 → 2 → 3까지 탐색한 뒤 3에서 4로 이동하려고 하면 이미 방문 처리되어 있기 때문에 탐색이 진행되지 않는다.

 

하지만 실제로는 1 → 2 → 3 → 4 경로 역시 탐색해야 한다.
방문 처리를 해버리면 이 경로를 고려하지 못하게 되는 것이다.

 

따라서 기존 코드에서 방문 처리를 제거한 뒤 다시 제출하니 정답 처리가 되었다.

---

코드

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):
    v1,v2 = map(int,input().split())
    graph[v1].append(v2)


S = int(input())

fan = [0 for _ in range(N+1)]

for f in list(map(int,input().split())):
    fan[f] = 1

if fan[1] == 1:
    print("Yes")
    exit()
    
queue = deque([(1,0)])

def bfs():

    while queue:
        v1, f = queue.popleft()
        cnt = 0
        for v2 in graph[v1]:

            if fan[v2] == 1:
                queue.append((v2,f+1))
            else:
                queue.append((v2,f))
            cnt += 1

        if not cnt and f == 0:
            return 'yes'
        
    return 'Yes'

print(bfs())

---

시간복잡도

• BFS의 시간복잡도는 $O(V+E)$ 이므로 약 $O(2*10^5)$의 시간복잡도를 가진다.