[백준] #2623 Python

백준 2623번 파이썬

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

아이디어

모든 보조 PD가 제시한 순서의 교집합에 해당하는 순서를 구하는 것이 목표.
결국 우리가 보고자 하는 그래프는 단방향 그래프이기 때문에 위상정렬을 사용한다.
각 순서를 그래프에 저장 + 각 노드의 진입차수 저장 후 위상정렬에 따라 q에 저장한다. 만약 위상정렬을 시킨 ans의 길이가 노드의 개수 이하일 때는 cycle이 있다는 뜻이며 이는 순서의 교집합이 존재하지 않는 경우를 뜻 함.

전체코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)


for i in range(M):
    lst = list(map(int, input().split()))
    for s in range(1, lst[0]):
        graph[lst[s]].append(lst[s+1]) #노드(s) -> 노드(s+1)
        indegree[lst[s+1]] += 1


q = deque()
ans = []
for i in range(1, N+1):
    if indegree[i] == 0:
        q.append(i) #진입차수가 0인 노드 넣기


while q:
    num = q.popleft()
    ans.append(num)
    for i in graph[num]:
        indegree[i] -= 1

        if indegree[i] == 0:
            q.append(i)


if len(ans) != N:
    print(0)
else:
    for i in ans:
        print(i)

느낀점

점점 문제를 보고 어떤 알고리즘을 떠올려야 하는지 약간 익숙해진 느낌이다.
단방향 그래프가 떠오른다 -> 위상정렬 고려!