[백준 2252 파이썬] 줄 세우기 (골드 3, 위상 정렬)

알고리즘 유형 : 위상 정렬
풀이 참고 없이 스스로 풀었나요? : 학습

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

소스 코드(파이썬)

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

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
inDegree = [0]*(N+1)

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

q = deque()

for s in range(1, N+1):
    if inDegree[s] == 0:
        q.append(s)

ans = []

while q:
    s = q.popleft()
    ans.append(s)
    
    for adj_s in graph[s]:
        inDegree[adj_s] -= 1
        if inDegree[adj_s] == 0:
            q.append(adj_s)

print(*ans, sep=" ")

풀이 요약

1. 이 문제는 학생들을 정렬해야하는데 그 기준을 살펴보면,

   학생들 사이에는 단방향 간선이 일부 존재하는데, 학생들을 일렬로 나열했을 때 이 간선이 역방향으로 나타나지 않도록 배치하면 된다.

   전형적인 위상정렬 활용 유형이다.

2. 우선 단방향 그래프를 2차원 리스트로 나타내준다.

   그리고 진입 차수를 나타내는 N+1 길이의 1차원 리스트가 하나 더 필요하다.

   진입 차수란, 외부에서 특정 노드로 들어오는 간선의 개수이다.

   예를 들어 종착 노드가 4인 단방향 간선이 1->4, 2->4 이렇게 두 개 존재하는 경우에, 4의 진입 차수는 2이다.

3. 로직은 이렇다.

   최초에 진입 차수가 0인 노드들을 큐에 넣는다.

   진입 차수가 0인 노드들을 뽑았을 때 수행할 내용은, 일단 뽑은 노드를 정답 리스트에 넣고, 그 노드의 인접 노드들의 진입 차수를 1 줄이고, 만약 진입 차수가 0이 됐다면 그 인접 노드를 큐에 넣는다.

   이 것을 반복하면 모든 노드를 단방향 관계를 만족하면서 나열할 수 있다.

   예를 들면, 학생이 3명이고, 간선이 1->3, 2->3 이라면,

   1의 진입 차수 : 0
   2의 진입 차수 : 0
   3의 진입 차수 : 2

   최초에 1과 2가 큐에 들어간다.

• 1을 뽑는다

  answer : [1]
  인접 노드인 3의 진입 차수 : 2-1 = 1

• 2를 뽑는다

  answer : [1, 2]
  인접 노드인 3의 진입 차수 : 1-1 = 0
  3을 큐에 넣어준다.

• 3을 뽑는다
  answer : [1, 2, 3]
  인접 노드가 없다.

  큐가 비었으므로 while 문 탈출.

  답은 [1, 2, 3]

배운 점, 어려웠던 점

• 위상 정렬을 배웠다. 생각보다 어렵진 않다.