위상 정렬

1. 위상 정렬이란?

• 방향이 있는 그래프(DAG, Directed Acyclic Graph)에서
• 사이클이 없고, 어떤 일들이 선후 관계를 가지고 있을 때
• 그 일들을 순서대로 정렬하는 것이 위상 정렬이야.

예시

예를 들어 과목 수강 순서가 있다고 해보자.

• 자료구조 → 알고리즘
• 수학 → 자료구조
• 영어 → 발표

이런 선후 관계가 있을 때,
가능한 순서는 수학 → 자료구조 → 알고리즘이야.
이처럼 "먼저 해야 할 일들을 고려해서 순서를 정하는 것"이 바로 위상 정렬이야.

---

2. 왜 DAG에서만 가능한가?

사이클(순환)이 있으면 어떻게 될까?

• A → B → C → A 이런 구조면
  무슨 일이 먼저인지 정할 수 없어.
  그래서 위상 정렬은 반드시 사이클이 없는 DAG에서만 가능해.

---

3. 위상 정렬은 어떻게 동작하나?

가장 기본적인 방법은 진입 차수(indegree)를 이용하는 거야.

예시 기반 Step by step

아래와 같은 수업 순서가 있을 때:

• 수학 → 자료구조
• 자료구조 → 알고리즘
• 영어 → 발표

이걸 기준으로 위상 정렬을 해보자.

1. 진입 차수 계산

과목	진입 차수
수학	0
자료구조	1 (수학→자료구조)
알고리즘	1 (자료구조→알고리즘)
영어	0
발표	1 (영어→발표)

2. 진입 차수 0인 과목을 큐에 넣어

→ 큐: [수학, 영어]

3. 큐에서 하나씩 꺼내서 처리해보자:

• 수학 꺼냄 → 결과에 추가 → 자료구조 진입 차수 줄임 (1→0) → 큐에 자료구조 추가
  → 큐: [영어, 자료구조]
• 영어 꺼냄 → 결과에 추가 → 발표 진입 차수 줄임 (1→0) → 큐에 발표 추가
  → 큐: [자료구조, 발표]
• 자료구조 꺼냄 → 결과에 추가 → 알고리즘 진입 차수 줄임 (1→0) → 큐에 알고리즘 추가
  → 큐: [발표, 알고리즘]
• 발표 꺼냄 → 결과에 추가
  → 큐: [알고리즘]
• 알고리즘 꺼냄 → 결과에 추가
  → 큐: [] (비어있음)

4. 최종 결과
   → [수학, 영어, 자료구조, 발표, 알고리즘]
   (※ 여러 가능한 정렬이 있을 수 있어)

---

4. Flowchart로 표현하면 이렇게 돼

[그래프 초기화] → [진입 차수 계산]
           ↓
[진입 차수 0인 노드를 큐에 삽입]
           ↓
[큐가 빌 때까지 반복]
     ┌────────────┐
     ↓            ↑
[큐에서 꺼내기]     |
     ↓            |
[정렬 결과에 추가]  |
     ↓            |
[연결된 노드 진입 차수 감소]
     ↓            |
[진입 차수 0 되면 큐에 추가]
     └────────────┘
           ↓
[정렬 결과 출력]

---

변수 & 함수명 정하기

꼭 필요한 변수명

변수명	설명	추천 이유
graph 또는 adj	인접 리스트 (그래프 구조)	각 노드의 연결 관계를 저장
in_degree 또는 indegree	각 노드의 진입 차수	위상 정렬의 핵심 변수
queue	진입 차수가 0인 노드를 담는 큐	BFS 방식에서 사용
result	위상 정렬 결과를 담는 리스트	최종 정렬 순서를 저장
N, V	노드 개수	노드 수를 의미함 (문제에 따라 다름)
M, E	간선 개수	간선 수를 의미함

---

함수명

함수명	역할	추천 이유
topological_sort()	위상 정렬을 수행하며 정렬된 노드 리스트를 반환	핵심 알고리즘을 분리할 수 있음
build_graph()	입력을 받아 그래프를 구성	입력과 그래프 구조를 분리
add_edge(a, b)	간선 추가 (a → b)	가독성 있는 그래프 구성

---

예시 구조 흐름

1. 그래프 초기화
   - 노드 번호가 1부터 시작한다고 가정
   - graph = [[] for _ in range(N+1)]
   - in_degree = [0] * (N+1)

2. 간선 입력 처리
   - graph[a].append(b)
   - in_degree[b] += 1

3. 큐 초기화 및 진입 차수 0인 노드 삽입
   - from collections import deque
   - queue = deque()
   - for i in range(1, N+1):
       if in_degree[i] == 0:
           queue.append(i)

4. 위상 정렬 수행 (topological_sort 함수)
   - 큐에서 노드를 꺼내서 result에 추가
   - 해당 노드가 가리키는 노드들의 in_degree를 1씩 줄임
   - 줄였을 때 0이 되면 다시 큐에 추가
   - 최종적으로 정렬된 노드 리스트 result를 반환

---

연습 겸 작성한 코드

import sys
from collections import deque

class answer:
    def __init__(self):
        self.n, self.m = map(int, sys.stdin.readline().split())
        self.graph = None
        self.in_degree = None
        self.queue = deque()
    
    def build_graph(self):        
        self.graph = [[] for _ in range(self.n + 1)]
        self.in_degree = [0] * (self.n + 1)

        # print(self.graph)

    def add_edge(self):
        for _ in range(self.m):
            a, b = map(int, sys.stdin.readline().split())
            self.graph[a].append(b) 
            self.in_degree[b] += 1

        # print(self.in_degree)

    def init_queue(self):
        for i in range(1, self.n + 1):
            if self.in_degree[i] == 0:
                self.queue.append(i) 

        # print(self.queue)

    def topological_sort(self):
        while len(self.queue) > 0:
            pop_dt = self.queue.popleft()
            print(pop_dt, end=' ')

            for next_node in self.graph[pop_dt]:
                self.in_degree[next_node] -= 1

                if self.in_degree[next_node] == 0:
                    self.queue.append(next_node)

ans = answer()
ans.build_graph()
ans.add_edge()
ans.init_queue()
ans.topological_sort()