[백준] #2252번 Topological Sorting python

문제 경로 :

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

2252번: 줄 세우기

 

위상정렬에 대한 백준 문제이다.

 

위상정렬(Topological Sorting) 이란?

 

문제 상황

-> 비순환 유향 그래프(DAG : directed acyclic graph)가 주어질 때 방향성을 거스리지 않게 모든 정점들을 나열하는 것

예제

• 프로젝트 관리
• 선수 과목
• 요리하기

위상정렬 특징

# 그래프가 사이클을 가질 경우 DAG를 만족하지 않아 위상정렬이 불가능합니다.

# 여러 개의 답이 존재할 수 있습니다.

# 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있습니다.

 

 

아래와 같이 python으로 문제 풀이를 하였습니다.

 

시간복잡도는 O(V + E) 입니다.

 

 

import sys
from collections import deque

N, M = map(int,sys.stdin.readline().rstrip().split())
height_students = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)

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

def topologicalSorting(height_students):
    data_queue = deque()
    result = []

    for i in range(1, N+1):
        if in_degree[i] == 0:
            data_queue.append(i)

    while data_queue:
        current_val = data_queue.popleft()
        result.append(current_val)

        for i in height_students[current_val]:
            in_degree[i] -= 1
            if in_degree[i] == 0:
                data_queue.append(i)
    for i in result:
        print(i, end=" ")


topologicalSorting(height_students)


'''
3 2
1 3
2 3
'''

 

 

 

Topological Sort를 풀어보았다.

 

이전에 했던 Network Flow 보다는 알고리즘이 이해하기 쉬웠다.

 

 

출처 : https://freedeveloper.tistory.com/390