[백준] 2252 : 줄 세우기 (파이썬)

위상정렬 문제

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

---

💡 풀이코드 (성공)

import sys 
from collections import deque 

V, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(V + 1)]
degree = [0] * (V + 1)

for i in range(E):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    degree[v2] += 1

def topological_sort(V, E, graph, degree):
    queue = deque()
    result = []

    for i in range(1, V + 1):
        if degree[i] == 0:
            queue.append(i)
    
    while queue:
        curr = queue.popleft()
        result.append(curr)

        for j in graph[curr]:
            degree[j] -= 1

            if degree[j] == 0:
                queue.append(j)
    print(*result)
topological_sort(V, E, graph, degree)

 

주요 로직

단방향 그래프 생성

방향성이 있는 그래프이므로 양방향이 아닌 단방향 그래프를 만들어준다. (양쪽의 정점에 추가 X)

for i in range(E):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    degree[v2] += 1

 

 

인접 노드 처리

• 큐를 돌며 인접 노드의 진입 차수를 1 감소시킨다.
• 그 후, 인접 노드의 진입 차수를 확인한다. 만약 진입 차수가 0이라면 큐에 삽입한다.

for j in graph[curr]:
    degree[j] -= 1

    if degree[j] == 0:
        queue.append(j)

 

밑의 사진에서 3 -> 4의 경우를 보며 코드를 이해해보자.

3 -> 4의 간선을 제거하여도 6 -> 4의 간선이 아직 남아있으므로 이 경우에는 진입 차수가 0이 되지 못한다. 

따라서, 4를 큐에 삽입하지 않고 일단 넘어간다. (4는 6 -> 4의 간선을 훑을 때 큐에 추후 삽입될 것)