[Python] 2252 - 줄 세우기

[Gold III] 줄 세우기 - 2252

[문제 링크](https://www.acmicpc.net/problem/2252)

🗝️알고리즘 분류

• 그래프 이론
• 위상 정렬

---

💻문제 정의

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

 

💡접근 및 설계

처음에는 그래프를 활용하여 너비 우선 탐색을 이용한 방법을 생각하였다. 키를 비교할 때, 큰 키를 가진 학생의 가중치를 더 주어 가중치 순서대로 출력하도록 설계할 생각을 하였다. 

 

위상 정렬이라는 새로운 개념을 알게되고 난 후, 위상 정렬을 이용해 문제에 접근하였다.

 

✏️알고리즘 풀이

N, M = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (N + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    indegree[B] += 1

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

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

    while Q:
        now = Q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for g in graph[now]:
            indegree[g] -= 1
            if (indegree[g] == 0):
                Q.append(g)

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

위상 정렬을 수행하는 코드이다.

 

위상 정렬의 과정은 다음과 같다.

1. 진입 차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때 까지 다음을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2. 진입 차수가 0이 된 노드를 큐에 새롭게 삽입

 

🗒️제출 코드

# 2252 줄 세우기

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

N, M = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (N + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    indegree[B] += 1

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

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

    while Q:
        now = Q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for g in graph[now]:
            indegree[g] -= 1
            if (indegree[g] == 0):
                Q.append(g)

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

topology_sort()

---