[백준/약점체크] 2252번: 줄 세우기

[문제]

 

[코드]

이 문제는 위상 정렬을 이용해서 풀면 된다. 위상 정렬에 대한 내용은 여기에 정리해 두었다.

https://woo-niverse.tistory.com/237?category=1038170 

정렬 알고리즘 : 위상 정렬 (Topological Sorting)

 

먼저, 큐를 이용한 방법

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
indegree = [0] * (N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topolgoy_sort():
    result = []
    q = deque()
    
    for i in range(1, N+1):
        if indegree[i] == 0:
            q.append(i)
            
    while q:
        now = q.popleft()
        result.append(now)
        for g in graph[now]:
            indegree[g] -= 1
            if indegree[g] == 0:
                q.append(g)
                
    print(*result)
    
topolgoy_sort()

 

스택을 이용한 방법

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)


def topolgoy_sort(graph):
    visited = [False for _ in range(len(graph))]
    result = []

    def DFS(node):
        if visited[node]:
            return
        visited[node] = True
        for adj in graph[node]:
              DFS(adj)
        result.append(node)
    
    for i in range(1, len(graph)):
        DFS(i)

    print(*result[::-1])
    
topolgoy_sort(graph)

- result.insert(0, node) 하고 result 를 그대로 출력해도 되지만 시간이 조금 더 소요된다!