[ 백준 / 2252 ] 줄 세우기

들어가는 말

 

알고리즘 문제 풀이, 백준 2252번 '줄 세우기' 문제입니다.

---

 

문제

 

N 명의 학생을 키 순서대로 정렬하는 문제다. 학생 A와 B가 주어졌을 때, A는 반드시 B의 앞에 위치하여야 하며 번호는 1부터 N까지 존재한다.

 

총 M회 비교하며, 정답이 여러 개인 경우 아무거나 출력해도 된다.

 

---

 

풀이

우선, 문제에서 'N명의 학생을 키 순서대로 줄을 세우려 한다' 하였다. 이는 일렬로 정렬한다는 말과 동일하다.

 

또한 A는 항상 B의 앞에 존재해야 하므로 반대의 경우는 존재할 수 없다. 즉, 방향성이 존재한다.

 

숫자들이 선형으로 연결되어 정렬되어야 하며, 방향성이 존재한다...?

 

아, 이 문제는 '위상 정렬'로 풀 수 있겠구나!

 

각 학생마다 작업 순서(차수, degree)를 지정한 다음, 작업 순서에 따라 결과값에 넣어주기만 하면 되겠다. 정답의 순서를 신경 쓸 필요가 없으므로 이 이상의 조건이 필요하지 않다.

 

이제 학생들의 번호를 입력 받아 그래프로 연결시켜 주고, 적절한 작업 순서를 부여한 다음, 그에 맞게 가공만 하면 된다. 자세한 내용은 코드로 살펴보자.

 

---

 

코드

import sys
from collections import deque
input = sys.stdin.readline

# 학생의 수 N, 비교횟수 M, 위상정렬 시 필요한 그래프 연결 리스트와 차수 리스트
n, m = map(int, input().split())
graphs = [[] for _ in range(n+1)]
degrees = [0] * (n+1)

# 비교할 학생을 입력 받아 그래프로 연결하고 뒤에 서야 하는 학생의 차수를 1 증가
for _ in range(m):
    a, b = map(int, input().split())
    graphs[a].append(b)
    degrees[b] += 1

# 차수가 가장 낮은 작업부터 수행해야 하므로 차수가 0인 학생들을 queue에 삽입
dq = deque([i for i in range(1, n+1) if degrees[i] == 0])

# 정답을 저장할 result
result = []

while dq:
    # 가장 먼저 들어간 학생을 정답 리스트에 저장
    cur_student = dq.popleft()
    print(cur_student)
    result.append(cur_student)
    
    # 현재 학생과 연결되어 있는 학생들의 차수를 1 감소하고, 차수가 0인 학생들을 다시 queue에 삽입
    for next_student in graphs[cur_student]:
        degrees[next_student] -= 1
        
        if degrees[next_student] == 0:
            dq.append(next_student)

# 순서를 신경 쓸 필요는 없으므로 별도의 정렬 조건은 추가할 필요 없다
print(*result)