위상정렬 (Topology sort)

from collections import deque def solution(v, graph, indegree): """ v: 노드 개수 e: 간선 개수 graph : a번째 리스트에 a노드에서 이동 가능한 노드들이 담겨있음 (2차원 리스트) indegree: 진입차수를 담은 리스트 """ answer = [] q = deque() # 큐 기능 위한 deque 라이브러리 # 1. 진입차수 0인 노드 큐에 삽입 for i in range(1, v+1): if indegree[i]==0: q.append(i) # 2. 큐가 빌 때까지 큐에서 원소 꺼내고 새롭게 진입차수가 0이 된 노드 큐에 넣기 while q: # 큐에서 원소 꺼내기 now = q.popleft() answer.append(str(now)) # 나중에 join연산으로 string으로 리턴하기 위해 str로 추가 # 해당 노드와 연결된 노드들의 진입차수에서 1 빼기 # 간선 제거 과정 for i in graph[now]: indegree[i] -= 1 # 이 과정에서 진입차수 0이 되는 노드를 큐에 삽입하면 # 이전에 이미 0이 된 노드 말고 이번 반복에서 0이 되는 노드만 큐에 추가 가늗 if indegree[i] == 0: q.append(i) answer = " ".join(answer) return answer # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0] * (v + 1) # 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화 graph = [[] for i in range(v + 1)] # 방향 그래프의 모든 간선 정보를 입력 받기 for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) # 정점 A에서 B로 이동 가능 # 진입 차수를 1 증가 indegree[b] += 1 print(solution(v, graph, indegree))

def dfs(node, graph, visited, stack): visited[node] = True # 현재 노드 방문했기에 visited값을 True로 바꿔주고 adj_v = graph[node] # 현재 노드에서 진출 가능 노드를 adv_j라 함 for u in adj_v: # 진출 가능한 노드들에 대해서 if not visited[u]: # 이 노드에 방문 아직 안했다면 dfs(u, graph, visited, stack) # 방문 stack.append(str(node)) def solution(v, graph): visited = [False for _ in range(v+1)] # 노드 방문 여부 stack = [] # 정렬 결과를 담을 stack for i in range(1, v+1): # 1노드부터 시작 if not visited[i]:# 이 노드를 방문하지 않았다면 dfs(i, graph, visited, stack) # dfs 수행 stack.reverse() stack = " ".join(stack) return stack # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0] * (v + 1) # 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화 graph = [[] for i in range(v + 1)] # 방향 그래프의 모든 간선 정보를 입력 받기 for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) # 정점 A에서 B로 이동 가능 # 진입 차수를 1 증가 indegree[b] += 1 print(solution(v, graph, indegree))