[Python 파이썬] 백준 25195번 - Yes or yes

2024년 8월 14일

문제 링크 : 백준 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$u$, v$v$ 가 주어진다. 이는 정점 u 에서 정점 v 로 가는 간선이 있음을 의미한다. (1 ≤ u, v ≤ N, u ≠ v)

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

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

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

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

출력

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

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 너비 우선 탐색

---

 

문제 접근

 

어느 경로를 통해 끝까지 탐색해도 팬클럽 곰곰이가 존재하는 정점을 하나라도 지나게 된다면 Yes를,

어느 한 경로라도 팬클럽 곰곰이가 존재하지 않는 경로로 이동할 수 있는 경우가 존재한다면 yes를 출력하면 되는 문제이다.

 

문제에서 주어진 단방향 그래프는 사이클이 없음이 보장되며, 두 정점을 연결하는 간선은 최대 한 개이다.

이 문제에서 해당 정보는 상당히 중요하다. 특정 경로에 존재하는 어느 정점을 탐색하고 있을 때 해당 정점이 이 경로의 끝, 즉 리프 노드인지 분별할 수 있는 기준이 명확해지기 때문이다.

 

다음은 본 문제의 2번째 입력데이터를 그래프화 한 것이다.

빨간색 정점은 팬클럽 곰곰이가 잠복해 있는 정점이다.

 

이를 인접리스트 형태로 나타내면 다음과 같다.

 

 

사이클이 존재하지 않기 때문에 리프 노드가 존재할 수 밖에 없으며, 해당 노드(정점)의 연결 정보는 비어있는 배열이게 된다. 만약 현재 탐색한 정점이 경로의 끝인 리프 노드인지 확인하려면 현재 노드에서 연결되어 있는 정보가 비어있는지만 확인하면 된다.

 

또한 두 정점을 연결하는 간선은 최대 한 개 이므로, 중복되는 연결 정보는 존재하지 않음을 유추해 볼 수 있다.

 

이를 통해 문제 접근법을 요약해보면 다음과 같다.

 

1. 1번 정점이 시작점이므로 1번 정점부터 그래프를 탐색한다. 나는 이 문제에서 탐색 알고리즘으로 DFS 방식을 택했다.

2. 현재 탐색한 정점이 리프 노드인지 체크한다. 만약 리프 노드까지 도달했다면 해당 경로는 팬클럽 곰곰이를 만나지 않는 경로이므로 yes를 출력하고 실행을 종료한다.

3. 현재 탐색한 정점에서 다음 정점을 탐색해보려 할 때, 다음 정점에 팬클럽 곰곰이가 존재한다면 해당 정점은 탐색하지 않고 넘어간다.

4. 만약 어느 경로로 가든 팬클럽 곰곰이를 만나게 되며 DFS 로직이 끝났다면, Yes를 출력한다.

---

입력 예제

 

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

 

출력 예제

 

yes

 

 

---

전체 코드

 

파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕다.

재귀의 최대 깊이를 계산하지 못하고 그대로 제출하면 다음과 같은 런타임 에러를 겪을 수 있다.

 

해당 문제에서는 재귀 깊이가 정점의 최대 개수인 100000개이므로 sys.setrecursionlimit(100001)로 지정해주어야 한다.

# 25195
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)

def dfs(now_v):
    if visited[now_v] or now_v in is_bear:
        return
    visited[now_v] = True

    if not graph[now_v]:
        print("yes")
        exit(0)

    for next_v in graph[now_v]:
        if next_v not in is_bear and not visited[next_v]:
            dfs(next_v)
            visited[next_v] = False

if __name__ == "__main__":
    N, M = map(int, input().split())

    graph = [[] for _ in range(N + 1)]
    visited = [False] * (N + 1)
    for _ in range(M):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)

    S = int(input())
    is_bear = {}
    s = list(map(int, input().split()))
    for _s in s:
        is_bear[_s] = True

    dfs(1)
    print("Yes")

 

---

풀이 후기

 

사이클이 존재하지 않는 그래프라는 점을 캐치해내어 생각보다 문제를 수월하게 풀 수 있었다.