Algorithm TIL 241026

백준 : 줄세우기 2252

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

 

 

문제 접근

• 우선 문제를 읽고 답이 여러가지가 나올 수 있는 게 신기했다. 문제를 해결 방안이 떠오르지 않아 한참 고민해보다가 알고리즘 분류를 보았다. 그러나 위상 정렬이라는 알고리즘을 잘 모르겠어서. 우선 알고리즘을 공부해야겠다고 생각했다.

 

위상 정렬이란?

• 순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 그 순서를 결정해주기 위해 사용하는 알고리즘이다.
• 위의 조건으로 인해 위상 정렬은 1️⃣ 사이클이 없는, 2️⃣ 방향이 있는 그래프인 경우에만 위상 정렬을 수행할 수 있습니다.
• 특이한 점은 위상정렬의 답은 여러가지가 나올 수 있다는 것입니다.
• 기본적인 구현 방법
  1. 우선, 각 노드마다 해당 노드로 진입할 수 있는 간선의 개수, 즉 진입차수를 입력합니다.
  2. 이후 위상정렬을 수행합니다.
     1. 진입차수가 0인 정점을 큐에 삽입합니다.
     2. 큐에서 원소를 꺼내 다른 정점으로 연결된 모든 간선을 제거합니다.
     3. 간선 제거 이후에 진입 차수가 0이라면 정점을 큐에 삽입합니다.
     4. 큐가 빌 때까지 2~3번 과정을 방문합니다. (만일 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것입니다.)
• 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬한 결과입니다.
• 위상정렬 알고리즘을 공부하고 난 뒤, 2252 문제는 어렵지 않게 풀 수 있었습니다. 비교하는 학생 a, 학생 b가 순차적으로 연결되어 있는 정점이라고 생각하고 문제를 풀었습니다.

 

위상 정렬의 시간복잡도 : O(V + E)

• 정점의 개수 + 간선의 개수 로 매우 빠른 알고리즘 중 하나입니다.

 

Python

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

n,m = map(int, input().split())
inDegree = [0] * (n+1) # 진입차수
arr = [[]for _ in range(n+1)]

# 학생 a가 학생 b의 앞에 서야한다는 그래프 정보 입력
for i in range(m) :
    a,b = map(int, input().split())
    arr[a].append(b)
    # 진입차수 1 증가
    inDegree[b]+=1
    
def topologySort() :
    result = []
    queue = deque()
    for i in range(1, n+1) :
        # 진입 차수가 0 인 학생들 큐에 삽입
        if inDegree[i] == 0 :
            queue.append(i)
    
    while queue :
        # 큐에서 원소 꺼내기
        x = queue.pop()
        result.append(x)
        # 원소와 연결된 다른 노드 확인
        for j in arr[x] :
            # 연결된 간선 제거
            inDegree[j] -= 1
            # 새롭게 진입차수가 0인 노드를 다시 큐에 삽입
            if inDegree[j] == 0 :
                queue.append(j)
    
    # 위상 정렬을 수행한 결과 출력
    for i in result :
        print(i, end=' ')
        
topologySort()

 

회고 및 느낀점

• 알고리즘에 대해서 알지 못했을 때, 풀수 있는 구현 능력을 좀 더 키울 수 있으면 좋겠다.
• 위상 정렬은 '순차가 있는 작업대로 정렬하는 알고리즘'이라고 기억해두자