[파이썬] 백준 25195 : Yes or yes (골드4)

[파이썬] 백준 25195 : Yes or yes (골드4)

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

---

풀이

방향성 생각

• 팬을 만나기 전 상태를 1, 만난 후 상태를 2라고 하면 1부터 전부 탐색했을 때 도착지점에 하나라도 도달할 수 있으면 성공이다.
• 1만 먼저 탐색하기 위해서 다익스트라 사용.
• 종료 조건 잘 생각하기.

코드

import heapq as hq
import sys

input = lambda : sys.stdin.readline().strip()
INF = float('inf')

N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)

K = int(input())
fans = set(map(int,input().split()))

if 1 in fans:
    print("Yes")
else:
    goal = set()
    V = [INF]*(N+1)
    V[1] = 1

    heap = [(1,1)]
    while heap:
        t,x = hq.heappop(heap)
        for nx in G[x]:
            if nx in fans:
                if 2 < V[nx]:
                    V[nx] = 2
                    hq.heappush(heap,(2,nx))
            else:
                if V[nx] == INF:
                    V[nx] = t
                    hq.heappush(heap,(t,nx))

            if not G[nx]:
                goal.add(V[nx])

    if 1 not in goal:
        print("Yes" if 2 in goal else "yes")
    else:
        print("yes")

---

코멘트

• 팬이 있는 노드를 거치고가면 실패라서 그냥 그 방향은 탐색하지 않으면 된다.
• 그냥 단순 BFS로 푸는 방식이 시간적으로 더 좋았을 듯 하다.