위상정렬 (그래프 정렬)

생성일: 2022년 3월 1일 오후 9:49

구현 코드

# 위상정렬(그래프 정렬)
import sys
sys.stdin = open("input.txt", "rt")

def adjacentVertex(v):
    l = []
    for i in range(n+1):
        if dis[v][i] == 1:
            l.append(i)
    return l

def DFS(v):
    visited[v] = 1
    adjacent = adjacentVertex(v)
    for x in adjacent:
        if visited[x] == 0:
            DFS(x)
    res.insert(0, v)

if __name__ == "__main__":
    n, m = map(int, input().split())
    dis = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for i in range(m):
        a, b = map(int, input().split())
        dis[a][b] = 1
    
    visited = [0]*(n+1)
    res = []

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

모범 답안

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
n, m=map(int, input().split())
graph=[[0]*(n+1) for _ in range(n+1)]
degree=[0]*(n+1) # 진입차수
dQ=deque()
for i in range(m):
    a, b=map(int, input().split())
    graph[a][b]=1
    degree[b]+=1
for i in range(1, n+1):
    if degree[i]==0:
        dQ.append(i)
while dQ:
    x=dQ.popleft()
    print(x, end=' ')
    for i in range(1, n+1):
        if graph[x][i]==1:
            degree[i]-=1
            if degree[i]==0:
                dQ.append(i)

차이점

• 내가 구현한 코드는 DFS를 활용하였다.
  • 연결된 노드들을 탐색하면서 정점(연결이 끊긴 노드)를 만나면 res의 앞에 넣는 형식이다.
• 모범 답안은 Queue를 사용하였다.
  • degree 리스트에는 각 노드들의 진입 차수를 저장한다.
    • 진입 차수란?
      • 2번 노드→3번 노드로 연결되어 있다면 3번노드의 진입 차수는 1이고,
        1번 노드→3번 노드로도 연결이 되있다면 3번노드의 진입 차수는 1증가한 2이다.
      • 즉, 본인을 가르키고 있는 노드의 개수이다.
  • 진입 차수가 0인 노드를 큐에 넣고 deque를하며 출력한다. deque를 하게 되면 해당 노드와 연결된 노드들의 진입 차수를 1씩 낮춘다.
  • 진입 차수가 0이된 노드를 큐에 넣고 같은 작업을 반복한다.