[백준 2252번 | 골드3] Python 풀이

 

문제를 보면 1 3, 3 2 이런식으로 두 개의 숫자를 주는데 왼쪽의 수가 오른쪽의 수보다 앞에 있어야 한다는 조건이 있다.

여기 이 문제가 위상정렬 문제임을 알 수 있다. (여러 가지 일이 있는데 이들 상호 간에 상호 선후 관계가 있을 때 위상정렬을 사용한다.)

위상정렬에서는 크게 두 가지 방법이 있다고 한다.

1. 진입 간선이 없는 정점을 선택하고 해당 정점과 연결되어 있는 정점 방문을 반복하면서 진출 간선을 하나씩 없애는 방법.

2. DFS(+백트래킹)

 

나는 2번 방식으로 풀어보았다. (시간나면 1번으로도 풀어서 수정하겠습니다.)

from collections import deque
import sys

input = sys.stdin.readline

def dfs(v):
    visited[v]=1
    for j in li[v]:
        if visited[j]==0:
            dfs(j)
    TS.appendleft(v)
    return

n, m = map(int, input().split())

#4 2 이런식으로 입력되면 4가 2보다 앞에 있으니 4에서 2로 간다고 생각
li = [[] for _ in range(n+1)]# Graph
for i in range(m):
    a, b = map(int, input().split())
    li[a].append(b)

visited = [0]*(n+1)# 방문기록을 위한 리스트
TS = deque()# TopologicalSort 결과를 저장할 덱 -> 백트래킹을 활용하기 때문에 dfs 특성상 끝까지 들어가서 정점이 저장되는 것을 역으로 생각해 appendleft로 순서유지

for i in range(1,n+1):
    if visited[i]==0:
        dfs(i)

print(*TS)

 

DFS로 주욱 들어갔다가 끝을 보면 돌아오면서 하나씩 저장(왼쪽으로)하는 것 밖에 없음.