[BOJ] Python 백준 Yes or yes(25195)

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

 

 

백트래킹을 통한 뚫린 길 찾는 완전 탐색 문제이다.

결론적으로 팬이 있는 길을 피해 끝까지 도달해야함으로

끝 도달 판단, 팬이 있는지 검증이 중요하다.

 

문제에서는 사이클이 존재하지 않는다고 했으므로, 끝으로 도달 하는 판단은 s[v]가 비어있으면 끝에 도달했다고 판단하면 된다.

이를 통해 팬 없이 s[v]가 0인 곳까지 오면 팬 없는 길이 존재한다는 뜻이 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N,M = map(int,input().split())

s= [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
    u,v = map(int,input().split())
    s[u].append(v)

F = int(input())
F_lst = list(map(int, input().split()))

chk = False
def dfs(v):
    global chk

    if v in F_lst:
        return

    if len(s[v]) == 0:
        chk = True
    else:
        for i in s[v]:
            if not visited[i]:
                visited[i] = True
                dfs(i)
                visited[i] = False


dfs(1)
if chk:
    print("yes")
else:
    print("Yes")

 

회고.

문제에서 사이클이 없다고 했는데 문제를 잘 읽지 않고 사이클이 존재하는 상태에서 끝점을 판단하는 방법을 고민하고 있었다...

문제를 잘 읽고 조건을 판단하는 노력을 더 해야겠다.