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

▶ 문제 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

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

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

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

 

▶ 접근 방법

위상 정렬을 사용하면 쉽게 해결할 수 있는문제였다.
다만, 위상 정렬을 코드로 어떻게 구현할 수 있을지가 중요했다.

초기값을 0으로 하는 진입차수 리스트를 만들었다.
이후, 학생들의 관계 정보를 해당 리스트에 넣어주어 진입차수를 변경하였다. 

이후 진입차수가 0인 학생을 큐와, 결과 리스트에 넣어주었다.
이후, 해당 학생과 인접한 학생들의 진입차수를 줄여가며 
다시 진입차수가 0이 되는 학생을 큐에 넣어 위의 과정을 반복하였다.

 

▶ 풀이 코드

import sys
from collections import deque

# 학생의 수와 키를 비교한 회수를 입력받는다.
N, M = map(int, sys.stdin.readline().split())

# 우선, 모든 학생에 대한 진입차수를 0으로 초기화 한다.
indegree = [0] * (N + 1)

# 학생들을 비교한 정보를 담기 위한 graph를 만든다.
graph = [[] for _ in range(N + 1)]

# 비교한 횟수만큼 정보를 넣어준다.
# vertex_A가 vertex_B보다 앞에 서야 한다는 의미로 넣었다.
# vertex_B의 진입차수를 증가시킨다.
# A < B인 경우, A -> B의 의미로 저장된 것이다. 
for _ in range(M):
    vertex_A, vertex_B = map(int, input().split())
    graph[vertex_A].append(vertex_B)
    indegree[vertex_B] += 1


# 위상 정렬 함수
def topology_sort():
    student_list = []
    queue = deque()

    # 학생들을 하나 씩 확인하면서
    for i in range(1, N + 1):
        # 진입차수가 0이라면 queue에 넣어준다.
        if indegree[i] == 0:
            queue.append(i)

    while queue:
        student = queue.popleft()
        student_list.append(student)
        
        # 해당 학생과 연결된 학생들의 진입차수를 줄인다.
        for adj_student in graph[student]:
            indegree[adj_student] -= 1
            if indegree[adj_student] == 0:
                queue.append(adj_student)

    # 위상 정렬 수행한 결과 출력
    for student in student_list:
        print(student, end=' ')

topology_sort()

 

▶ 관련 링크

2021.11.20 - [알고리즘] - 위상 정렬(Topological Sort)이란?