BOJ - 2252

백준 문제 링크
줄 세우기

❓접근법

1. 줄 세우기
   -> 위상 정렬 알고리즘 사용
   그래프상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를
   지키는 전체 순서를 계산할 수 있다.

• 위상 정렬의 과정은 다음과 같다.
• 진입차수가 0인 노드를 큐에 넣는다.
• 큐가 빌 때까지 다음의 과정을 반복한다.
  • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
  • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

2. 진입 차수를 넣을 변수 indegree = [0] * (n + 1) 를 만든다.
   graph를 만들어 A,B를 넣어주고 A가 B보다 앞서기 때문에
   indegree[B] += 1 한다.
3. 위상 정렬 함수를 만들건데,
   순서를 저장할 빈 리스트 result를 만들고,
   indegree를 돌면서 차수가 0이면 큐에 넣어준다.
4. 큐가 비어있을 때까지 원소를 빼서 살펴본다.
   원소는 result에 넣어주고,
   해당 원소와 연결된 노드들의 진입차수를 1 빼주고,
   새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
5. 마지막으로는 result 를 출력하면서 함수를 마무리한다.
6. 함수를 실행하면 리스트가 나오므로 문제의 출력 형식에 맞춰 출력하면 끝!

👌🏻코드

from collections import deque

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)

for _ in range(m):
   a, b = map(int, input().split())
   graph[a].append(b) # A가 B 앞에 서있어야 하므로
   
   indegree[b] += 1 # 진입차수 1 증가
   
def topology_sort():
   
   result = []
   
   queue = deque()
   
   for i in range(1, n + 1):
       if indegree[i] == 0:
           queue.append(i)
           
           
   while queue:
       now = queue.popleft()
       result.append(now)
       
       for i in graph[now]:
           indegree[i] -= 1
           if indegree[i] == 0:
               queue.append(i)
               
   return result

print(*topology_sort())