(Python/파이썬) 백준 2252 - 줄 세우기

문제출처: https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

1. 코드:

import sys
import sys 
from collections import deque
 
 
n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
degree = [0] * (n+1) # 진입 차수 리스트
 
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1
 
#위상 정렬 알고리즘
queue = deque() # 큐 생성
for i in range(1, n+1):
    if degree[i] == 0:
        queue.append(i)
ans = []
while queue :
    now = queue.popleft()
    ans.append(now)
    for i in graph[now]:
        degree[i] -= 1
        if degree[i] == 0 :
            queue.append(i)
for a in ans:
    print(a, end=' ')

2. 해결과정:

전형적인 위상 정렬 문제이고, 각 학생들의 키 비교를 진입 차수로 생각했다. 따라서, 방향성이 있는 그래프로 보고 풀면 위상정렬 알고리즘으로 풀 수 있다. 각 노드에 진입 차수를 의미하는 리스트를 만들어준다.  그래프는 방향성을 가지므로 a -> b 일 경우 a인덱스에 b를 넣는 방식을 택하였고, 이 때 b는 진입차수가 1씩 증가하게 된다. 진입차수가 0인 것들을 제거해나가면서 그 숫자를 앞에 가졌던 숫자들은 진입차수가 1씩 감소하게된다. 0이되면 큐에 넣어서 동일한 작업을 반복한다.

 

3. 느낀점:

위상정렬이 생각보다 감이 잘 안온다.