[백준] 2252. 줄 세우기 - 파이썬

[Gold III]

 

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

2252번: 줄 세우기

 

풀이

[백준] 1005. ACM Craft - 파이썬

[백준] 2056. 작업 - 파이썬

최근 위 문제들과 같은 위상 정렬 문제를 몇 번 풀어서인지,

문제를 보고 얼마 지나지 않아 위상 정렬로 해결할 수 있겠다는 생각이 들었다.

 

모든 vertex가 edge로 연결되어 있지도 않고, "답이 여러 가지인 경우에는 아무거나 출력한다." 라는 조건까지 있기 때문에, 오히려 위 두 문제보다 난이도가 쉽다고 느껴졌다. 기본적인 위상 정렬 구현만 제대로 했다면 풀리는 문제인 것 같음!

 

from collections import deque
N, M = map(int, input().split())

graph_in_cnt = dict(zip([i for i in range(1, N+1)], [0 for _ in range(N)]))
graph_in = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))
graph_out = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))

for i in range(M):
    a, b = map(int, input().split())
    graph_in_cnt[b] += 1
    graph_in[b].append(a)
    graph_out[a].append(b)

queue = deque()
for g in graph_in_cnt:
    if graph_in_cnt[g] == 0:
        queue.append(g)

result = []
while queue:
    a = queue.popleft()
    result.append(a)

    for k in graph_out[a]:
        graph_in_cnt[k] -= 1
        if graph_in_cnt[k] == 0:
            queue.append(k)

print(*result)