백준 줄 세우기 파이썬(Python) 풀이

문제

• 백준 줄 세우기
• 난이도: Gold3
• https://www.acmicpc.net/problem/2252

풀이 알고리즘: 위상 정렬

이 문제를 풀이한 과정과 접근법을 공유함니다.

1. N명의 학생을 줄 세우려는데 일부 학생의 순서만 알고 있다면 이것은 위상 정렬로 풀 수 있는 문제다.
2. 위상 정렬은 중간 연결 순서가 정해진 순서를 정렬할 때 효과적인데 이 문제는 마침 일부만 순서가 정해져 있다.
3. graph를 통해 순서를 입력 받고 진입차수를 초기화한다.
4. 진입 차수가 0인 것들을 큐에 넣고 진입차수가 새롭게 0이 되면 다음 큐의 끝에 넣는다.
5. 큐가 아예 빌 때까지 순회한다.
6. 순회하면서 출력하면 그것이 정답이다.

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

# 위상 정렬로 문제를 풀 수 있어 보인다.
graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

# 진입 차수가 0인 것들을 큐에 넣는다.

q = []
for i in range(1, n+1):
    if indegree[i] == 0:
        q.append(i)

while q:
    next_q = []
    for now in q:
        print(now, end=' ')
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                next_q.append(i)
    q = next_q

후담

필자는 예전에 위상정렬로 풀면 안되는 카카오 코딩테스트의 양과 늑대가 나왔던 문제를 위상정렬로 풀었었다.

위상정렬을 알지도 못할 때 적용해서 풀어보려고 했다가 코딩테스트에서 낭패를 본 적이 있었는데 위상정렬이란걸 제대로 알게 되고 어떨 때 이와 같이 접근해야 하는지 확실히 알아가자.