[파이썬] 백준 26146 : 즉흥 여행 (easy) (플레5)

[파이썬] 백준 26146 : 즉흥 여행 (easy) (플레5)

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

---

풀이

방향성 생각

• 어떤 노드에서 출발하든 모든 노드를 방문할 수 있어야 한다.
  • 모든 노드가 하나의 SCC의 component인 경우이다.
  • 따로 응축그래프를 만들고 진입차수를 계산하거나 BFS를 돌릴 필요가 없다.

 

---

파이썬

from collections import deque
import sys
sys.setrecursionlimit(10**6)

input = lambda : sys.stdin.readline().strip()

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)


V = [-1]*(N+1)
P = [-1]*(N+1)
counter = [0]
stack = deque()
on_stack = [False]*(N+1)

SCC = []
def dfs(x):

    V[x] = counter[0]
    P[x] = counter[0]
    counter[0] += 1
    stack.append(x)
    on_stack[x] = True

    for nx in G[x]:
        if V[nx] == -1:
            dfs(nx)
            P[x] = min(P[x],P[nx])
        elif on_stack[nx]:
            P[x] = min(P[x],V[nx])

    if V[x] == P[x]:
        scc = []
        while True:
            w = stack.pop()
            on_stack[w] = False
            scc.append(w)
            if w==x:
                break
        SCC.append(scc)

for x in range(1,N+1):
    if V[x]==-1:
        dfs(x)
print('Yes' if len(SCC) == 1 else 'No')

---

코멘트

• 파이썬이 자료형이 편해서 대충대충 짜느라 2D 배열 좌표를 1차원으로 반환하는 방식은 잘 안썼는데, 굳이 사이즈 크게 튜플로 할당하거나 ArrayList 쓰는 방식보다는 간단하게 i*W+j로 반환하는게 더 나은 듯 하다.