[알고리즘] BOJ 2252 줄 세우기 #Python

[BOJ] 2252 줄 세우기 바로가기

📍 문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

---

📍 입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

---

📍 출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

---

📍 풀이

🧷 풀이 과정

📒 위상 정렬 (Topological Sorting) 알고리즘의 개념에 대한 정보는 요기!

위상 정렬 알고리즘은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.
BOJ 2252번: 줄 세우기 문제에서의 순서는 학생의 키이다.

✍ 코드

# BOJ 2252 줄 세우기
# https://www.acmicpc.net/problem/2252

from sys import stdin
from collections import defaultdict, deque

def solution(N, AB):
    answer = []

    graph = defaultdict(list) # 정점 연결 정보
    degree = [0 for i in range(N+1)] # 정점 진입 차수

    for A, B in AB:
        degree[B] += 1 # 정점 진입 차수 갱신
        graph[A].append(B) # 정점 연결 정보 갱신

    # 진입 차수가 0인 정점으로 구성된 우선순위 큐 생성
    queue = deque()
    for i in range(1,N+1):
        if degree[i] == 0:
            queue.append(i)
    
    # 위상 정렬
    while queue:
        node = queue.popleft()
        answer.append(node) 
        # 현재 정점(node)에 연결된 모든 정점(nextNode)
        for nextNode in graph[node]:
            # 연결된 정점(nextNode)의 진입차수 -1
            degree[nextNode] -= 1
            # 진입 차수가 0인 즉, 현재 자신보다 큰 학생이 없는 경우
            if degree[nextNode] == 0:
                # queue에 추가
                queue.append(nextNode)

    return answer

N, M = map(int,stdin.readline().split())
AB = [list(map(int,stdin.readline().split())) for _ in range(M)]

result = solution(N, AB)
print(*result)