[Python] 백준 2252 줄세우기

 

1. 문제 링크

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

2252번: 줄 세우기

 

2. 문제 요약

• 학생들을 키 순서대로 줄을 세운 결과를 출력한다.

 

3. 아이디어 정리

• 위상 정렬

1. 진입 차수가 0인 모든 노드에 큐 넣기
2. 큐가 빌 때까지 반복
   • 큐에서 한 개 빼고 결과에 넣기
   • 큐에서 원소를 꺼내 나가는 간선 제거
   • 새롭게 진입차수가 0이 된 노드에 큐 넣기

 

4. 문제 풀이

4-1. 내풀이

import sys
from collections import deque

def topology_sort():
    result = []
    q = deque()
    # 1. 진입차수가 0인 모든 노드를 큐에 넣는다.
    for i in range(n):
        if indegree[i] == 0:  # 처음은 진입차수가 0인 것부터. 진입차수 0이 시작하는 노드이기 때문
            q.append(i)
    # 2. 큐가 빌 때까지 아래 과정 반복한다.
    while q:
        # 2-1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
        now = q.popleft()
        result.append(now + 1)
        for i in graph[now]:   
            indegree[i] -= 1
            if indegree[i] == 0: # 2-2. 새롭게 진입차수가 0이된 노드를 큐에 넣는다.
                q.append(i)

    print(*result)

n, m = map(int, sys.stdin.readline().split())  # 학생 수, 키를 비교한 수
indegree = [0] * n
result = [1] * n
graph = [[] for i in range(n)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a - 1].append(b - 1)  # a > b
    indegree[b - 1] += 1    # 진입 차수

topology_sort()

 

 

5. 결론

• 위상 정렬 문제