이코테 강의를 통해서 공부했습니다!

위상 정렬

• 위상 정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

진입차수와 진출차수

• 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 알고리즘

• 큐 or dfs를 이용한다.
• 큐를 이용하는 위상 정렬 알고리즘의 동작 과정

  1. 진입차수가 0인 모든 노드를 큐에 넣는다.

  2. 큐가 빌 때까지 다음의 과정을 반복한다.
     1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
     2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

     ⇒ 결과적으로 **각 노드가 큐에 들어온 순서 == 위상 정렬을 수행한 결과**가 된다!

위상 정렬 코드

# 위상 정렬 알고리즘

from collections import deque

# 입력 및 초기화
num_node, num_edge = map(int, input().split())

indegree = [0] * (num_node + 1)             # 각 노드의 진입 차수
graph = [[] for i in range(num_node + 1)]   # 각 노드의 간선 연결 정보 (graph[a][b] : a->b 연결)
for _ in range(num_edge):
    a, b = map(int, input().split())
    graph[a].append(b)  # a->b 연결
    indegree[b] += 1

# 위상 정렬 함수
def topology_sort():
    result = []     # 알고리즘 수행 결과
    q = deque()

    # 큐 초기화 : 진입 차수가 0인 노드
    for i in range(1, num_node + 1):
        if indegree[i] == 0:
            q.append(i)

    # q가 빌 때까지
    while q:
        now = q.popleft()   # 큐에서 꺼낸 노드
        result.append(now)
        # now에서 나오는 간선 제거
        for i in graph[now]:
            indegree[i] -= 1
            # 진입차수가 0이 됐다면 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
        
    # 결과 출력
    for node in result:
        print(node, end=' ')

topology_sort()

'''
입력
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
'''
'''
출력
1 2 5 3 6 4 7
'''

위상 정렬의 특징

• 위상 정렬은 DAG(Directed Acyclic Graph)에 대해서만 수행할 수 있다.
• 위상 정렬에는 여러 가지 답이 존재할 수 있다.
  • 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 해당
• 모든 원소를 방문하기 전에 큐가 빈다면 → 사이클이 존재한다고 판단할 수 있다.
  • 사이클에 포함된 원소는 절대 큐에 들어갈 수 없다.
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행하는 방법도 있다.

위상 정렬 알고리즘 성능 분석

• 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거하는 연산 → 시간 복잡도 O(V+E)

백준 문제

2623번 : 음악 프로그램

2623번: 음악프로그램

솔루션 아이디어

• 위상 정렬인데 입력을 받는 방식이 조금 다르다
• 2252번 문제에서 그래프를 입력하는 방식을 바꾸고, 위상 정렬이 불가능한 경우까지 고려하여 코드를 작성해야 한다.
• 그래프 입력 방식
  • 보조 pd가 입력한 순서대로 단 방향의 트리가 하나 만들어진다
  • 보조 pd들이 입력한 정보를 모두 합쳐 그래프로 기록하면 된다.
  • 예를 들어, 입력이 예시와 같다면 아래와 같이 그래프를 만들어주면 된다
    1 4 3
    6 2 5 4
    2 3
  

• 위상 정렬이 불가능한 경우
  • q가 빌 때까지 코드를 돌렸는데 모든 노드를 정렬하지 못했다면 (정렬하다 중간에 끝났다면) 위상 정렬이 불가능한 경우이다.
  • len(result) == num_node 가 성립하면, 위상 정렬이 가능하고 그렇지 않다면 불가능하다.

솔루션 코드

# 음악 프로그램

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

# 입력 및 초기화
num_node, m = map(int, input().split())

indegree = [0] * (num_node + 1)             # 각 노드의 진입 차수
graph = [[] for i in range(num_node + 1)]   # 각 노드의 간선 연결 정보 (graph[a][b] : a->b 연결)

# 보조 pd의 정보를 바탕으로 그래프 입력
for _ in range(m):
    order = list(map(int, input().split()))
    for i in range(1, order[0]):
        graph[order[i]].append(order[i + 1])
        indegree[order[i + 1]] += 1

result = []     # 알고리즘 수행 결과
q = deque()

# 큐 초기화 : 진입 차수가 0인 노드
for i in range(1, num_node + 1):
    if indegree[i] == 0:
        q.append(i)

# q가 빌 때까지
while q:
    now = q.popleft()   # 큐에서 꺼낸 노드
    result.append(now)
    # now에서 나오는 간선 제거
    for i in graph[now]:
        indegree[i] -= 1
        # 진입차수가 0이 됐다면 큐에 삽입
        if indegree[i] == 0:
            q.append(i)

# 출력
# 위상 정렬이 가능한지 확인
if len(result) == num_node:
    for node in result:
        print(node)
else:
    print(0)