[BOJ] 2252번 : 줄 세우기(위상 정렬)

목차

접근

이름에서부터 풍겨오는 위상정렬의 냄새.

그냥 아주 간단한 위상정렬 문제이다.

위상정렬에 관한 내용은 이전 문제를 참고해보자.

2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp)

[BOJ] 1005번 : ACM Craft(위상 정렬, dp)

간단하게 설명하자면, 위상정렬은 BFS 탐색과는 거의 비슷하지만, "진입차수"라는 차별적인 요소를 이용해서 순서에 맞춰서 그래프 탐색을 진행하는 알고리즘이다. 입력에 있어서 체크할 것들의 리스트는 아래와 같다. 

입력으로 "A B" 가 들어온 것을 "A가 B의 앞에 위치 해야한다" 라는 조건으로 해석한다면

• A -> B로 이어진 간선을 생성한다.
• 차후에 방문해야하는 B는 진입차수를 1 늘려준다.

입력단에선 이 두개의 조건을 생각해서 입력을 받아야한다.

 

그리고 Queue에 진입차수가 0인 노드들부터 먼저 다 집어넣고, 순회를 시작한다.

순회를 진행하면서, 방문하는 노드의 진입차수를 감소시키고, 진입차수가 0이 되었다면 Queue에 추가한다.

 

이렇게 해서 위상 정렬을 이용해서 간단하게 문제를 해결할 수 있다.

 

해결

위상정렬을 이용해서 방문하는 노드들을 출력하자.

 

코드

from collections import deque, defaultdict
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
orders = defaultdict(int)
graphs = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    graphs[a].append(b)
    orders[b] += 1
    
que = deque()
for i in range(1, N+1):
    if not orders[i]:
        que.append(i)
        
while que:
    v = que.popleft()
    print(v, end=" ")
    for nv in graphs[v]:
        orders[nv] -= 1
        
        if orders[nv] == 0:
            que.append(nv)