Juneer Blog

실전 문제풀이(그래프 이론)

 
  • Sep 05, 2022

2252번 (줄 세우기)

출처: 백준
난이도: 골드 3

애초에 문제 분류가 위상 정렬로 되어 있지 않았다면 못 풀엇을 문제이다…

모든 노드를 나열하는데 방향성이 있게 제약조건이 있다는 것에서 위상 정렬이라는 힌트를 얻으면 좋을 것 같다.

  • 내 풀이
import sys
from collections import deque

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

# 연결 정보 및 진입차수 초기화
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
for _ in range(M):
  a, b = map(int, sys.stdin.readline().rstrip().split())
  graph[a].append(b)
  indegree[b] += 1



def topology_sort():
  q = deque()

  # q에 진입차수 0인것 넣기
  for i in range(1, N+1):
    if indegree[i] == 0:
      q.append(i)
      
  while q:
    now = q.popleft()
    print(now, end=' ')  # 현재 방문한 노드 출력

    # i는 연결된 노드
    for i in graph[now]:
      # 연결된 간선 제거 작업
      indegree[i] -= 1

      # 진입차수가 0인 연결노드가 발견되면 q에 넣기
      if indegree[i] == 0:
        q.append(i)

topology_sort()
Search