less than 1 minute read

문제

접근 방법

정해진 순서대로 특정 시작점에서부터 다른 점들까지의 최단 거리를 구하는 알고리즘을 생각해내야 하는데 아는건 Topological sort 밖에 없어서 이 방법으로 해결하였다.

Topological sort는 임의의 노드 A 로 향하는 노드들이 0개일 때, A의 순서가 다가왔다고 판단하여 A에 대해서 다른 노드들로 뻗어나가는 알고리즘이다. 그러기 위해서는 각 노드를 향해 가는 노드 개수인 inorder 값을 모든 노드에 대해 저장해야 한다.

이때, 실수한게 있는데 pop을 할 때마다 학기가 바뀐다는 생각을 한 것이다. 동시에 inorder 값이 0이 된 애들이 있을 수도 있는데 1->2->3의 경우만 생각하고 코드를 짰다.

해결하기 위해서 순서가 이제서야 다가왔을 때, 현재 학기에서 +1을 하여 다음 학기에 듣는 과목들을 표시하였다.

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

'''
정해진 순서로 갔을 떄 최소 거리를 구하는 알고리즘은 위상 정렬
'''

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
ins = [0]*(n+1)

for _ in range(m):
  a,b = map(int, input().split())
  graph[a].append(b)
  ins[b]+=1

def topological_sort():
  nexts = deque()
  result = [0]*(n+1)

  #inorder 0인 애들 찾기 (시작점)
  for start in range(1,n+1):
    if ins[start]== 0:
      nexts.append(start)
      result[start] = 1
      
  while nexts:
    cur = nexts.popleft()
    for next in graph[cur]:
      ins[next]-=1
      # 순서가 왔다면, queue에 저장
      if ins[next]==0:
        nexts.append(next)
        result[next] = result[cur]+1
  return result[1:]

print(*topological_sort())

You May Also Enjoy