백준 2252번: 줄세우기 - 위상정렬

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

 

위상정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘입니다.

 

예를 들어 A의 작업보다 B의 작업이 먼저 처리 되어야하고, C의 작업이 A의 작업보다 먼저 처리 되어야 한다면

C - A - B 의 순서대로 일을 처리해야 할 것입니다.

 

A의 작업보다 B의 작업이 먼저 처리 되어야하고, C의 작업도 B의 작업보다 먼저 처리 되어야 한다면

A - C - B 도 되고, C - A - B 도 됩니다.

 

그래서 위상정렬 특성상 별 다른 조건이 없을 경우 여러 답이 나올 수 있습니다.

 

이제 위에서 얘기한 "작업"을 학생들의 "키"로 생각해보겠습니다.

학생 A의 키가 B보다 크고, C의 키가 A보다 크다는 정보를 갖고 줄을 세우면

B - A - C (작은 순서부터) 순으로 줄을 세울 수 있습니다.

 

문제에서도 모든 학생의 키를 직접 재서 정렬하지 않고, 위와 같이 일부 학생의 키를 비교하여 정렬하려고 하기 떄문에 위상정렬을 통해 줄을 세워야합니다.

 

 

우선 각 학생의 indegree를 알아야합니다. 여기서 indegree는 키를 비교했을 때 자기 앞에 와야만 하는 학생의 수를 기록해 놓은 것입니다.

 

A가 B보다 앞에 와야한다.

C가 B보다 앞에 와야한다.

 

위의 조건에서 예를 들어보면, A와 C는 둘 중 누가 먼저와도 상관이 없고, B는 A와 C가 모두 줄을 선 이후에 줄을 설 수 있습니다.

여기서 B는 indegree가 2이고, A와 C는 둘다 0입니다.

 

이 indegree가 0이라면 시작점이 될 수 있고, indegree 값이 0인 A와 C중 하나가 맨 앞에 서게 되는 것입니다.

 

만약 A를 줄 세우게 되면 B의 indegree는 1을 줄여 1이 됩니다. (아직 C가 남아있기 때문에)

C가 줄을 서게 되면 그제서야 B는 indegree가 0이 되고 줄을 설 수 있게 됩니다.

 

indegree를 기록하면서, 어느 학생으로부터 온 indegree인지도 기록해야합니다.

ex) A → B 일 경우 students['A'].append('B')

 

n, m = map(int, stdin.readline().split())
students = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]
result = []

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

 

indegree list를 돌아주면서 값이 0이면 queue에 넣습니다.

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

 

그 다음 n명의 학생이 있다면, n번의 사이클을 돌면서 정렬을 해줄 것입니다. 만약 n번 돌기 전에 queue에 값이 없다면 사이클이 발생한 것이므로 위상정렬이 될 수 없는 구조입니다.

 

queue를 pop하고 result에 넣습니다.

그 후 해당 학생과 직접 키를 비교하여 더 뒤에 와야되는 학생들을 파악합니다.

그 학생의 indegree를 1 줄이고, 만약 줄인 값이 0이라면 queue에 넣어줍니다.

앞의 학생은 이미 result에 들어갔고, 그 다음 학생의 indegree를 1 줄여서 0이 되었다면 그 학생보다 앞에 올 학생이 더 이상 없다는 뜻이기 때문에 queue에 들어가게 되는 것입니다.

 

for i in range(1, n+1):
    if not dq:  # 사이클발생
        break
    current = dq.popleft()
    result.append(current)
    for j in students[current]:
        indegree[j] -= 1
        if indegree[j] == 0:
            dq.append(j)

 

전체코드

from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
students = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]
result = []

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

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

# 위상정렬
for i in range(1, n+1):
    if not dq:  # 사이클발생
        break
    current = dq.popleft()
    result.append(current)
    for j in students[current]:
        indegree[j] -= 1
        if indegree[j] == 0:
            dq.append(j)

print(*result)