백준 / 1766번 / 문제집 / python 파이썬

 

문제 : https://www.acmicpc.net/problem/1766

 

 

---

나의 풀이

import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
first = [[] for _ in range(n+1)]
link = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    first[a].append(b)
    link[b] += 1

hq = []
for i in range(1, n+1):
    if link[i] == 0:
        heapq.heappush(hq, i)

while hq:
    node = heapq.heappop(hq)
    print(node, end=" ")
    for x in first[node]:
        link[x] -= 1
        if link[x] == 0:
            heapq.heappush(hq, x)

 

이 문제는 위상 정렬을 사용하여 풀어야 하는 문제이다. 

위상 정렬이란, 정렬 알고리즘의 일종으로 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서 정점들의 선형 순서를 찾는 알고리즘이다.

 

위상 정렬 알고리즘은 다음과 같다.

1. 진입 차수가 0인 노드를 큐에 넣는다.
2. 큐에서 노드를 하나씩 꺼내 결과 리스트에 추가한다. ( 이 노드에서 연결된 모든 노드의 진입 차수를 1씩 줄인다.)
3. 큐가 빌 때까지 반복을 수행하고 결과 리스트에 모든 노드가 담기면 완료된다.

- 사이클이 존재하면 위상 정렬은 불가능하다.

 

위 코드에서 

인접 리스트 (first)로 각 노드가 가리키는 다른 노드들을 저장하고, 

for _ in range(m):
    a, b = map(int, input().split())
    first[a].append(b)
    link[b] += 1

 

link 배열에 각 노드의 진입 차수를 저장한다.

 

hq = []
for i in range(1, n+1):
    if link[i] == 0:
        heapq.heappush(hq, i)

진입 차수가 0인 노드를 찾아 hq에 추가한다. 

 

while hq:
    node = heapq.heappop(hq)
    print(node, end=" ")
    for x in first[node]:
        link[x] -= 1
        if link[x] == 0:
            heapq.heappush(hq, x)

파이썬의 heapq는 최소 힙을 사용하기 때문에 항상 가장 작은 값을 먼저 꺼내므로 hq에서 값을 꺼내 node에 저장 후 출력하고, node에 연결된 모든 노드 x에 대해 진입 차수 1을 뺀다. 만약 진입 차수가 0이 된 노드가 있다면 hq에 추가한다.