백준 2252번 줄 세우기

백준 2252번 줄세우기

문제: https://www.acmicpc.net/problem/2252

코드

import sys
from collections import deque

def makeLine():
  for i in range(M):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    degree[end] += 1

def order():
  startList = []
  for i in range(1, N+1):
    if degree[i] == 0:
      startList.append(i)

  queue = deque()
  queue.extend(startList)
  while queue:
    node = queue.popleft()    
    if f"{node}" not in visited:
      for end in graph[node]:
        degree[end] -= 1
        if degree[end] == 0:
          queue.append(end)

      visited.append(f"{node}")

N, M = map(int, sys.stdin.readline().split())

graph = {i : [] for i in range(1, N+1)}
degree = [0 for _ in range(N+1)]
visited = []

makeLine()
order()

print(" ".join(visited))

문제풀이

줄 세우는 알고리즘은 줄을 잘 세우다가도 root의 순서가 바뀌어버리면 밑에 따라오던 자식 노드들까지 순서가 바뀌는 경우가 생긴다.

따라서 일반적인 리스트를 따라서 문제를 적용하기 보다는 그래프를 이용해서 푸는게 맞다.

알고리즘 흐름

1. 주어진 비교시스템을 활용해서 단방향 그래프를 작성한다.
2. 각 노드별로 진입차수를 구하여 저장한다.
3. 진입차수가 0인 노드부터 시작해서 위상정렬을 사용한다.

위상정렬

그래프가 있을 때 해당 노드로 들어오는 간선의 개수를 구하여 진입차수로 나타낸 다음 정렬하는 방법이다.

진입차수가 0인 노드부터 순서대로 알고리즘을 따라가는데 다음과 같다.

1. 해당 노드에서 부터 연결된 간선을 모두 제거한다.
2. 만약 간선이 제거되면서 진입 차수가 0이 된 노드가 있다면 해당 노드를 큐에 넣어준다.
3. 큐가 끝날때 까지 이를 반복한다.

• 이때 위상정렬은 진입차수가 0인 노드가 여러개라면 어떤 노드를 먼저 큐에 넣고 실행하는가에 따라서 순서의 결과가 달라질 수 있다는 점을 유의해야한다.