알면 도움되는 코딩 테스트 유형: 15) #Topological_Sorting

• 이번에는 IT 기업 코딩 테스트에서 가끔씩 등장하곤 하는 유형 중 하나인 "위상 정렬"에 대해 이야기해보려고 합니다. 위상 정렬은 그래프 이론의 개념으로, 방향 그래프에서 각 노드들의 선행 순서를 지켜주는 정렬 방법입니다.

 

위상 정렬이란?

 

• 위상 정렬은 일종의 선후 관계를 가진 작업들을 순서에 맞게 나열하는 알고리즘입니다. 주로 작업 스케줄링, 종속성 관리, 컴파일러 등 다양한 분야에서 활용됩니다.
• 간단하게 설명하자면, 방향 그래프(Directed Graph)에서 각 노드들 사이의 선후 관계가 주어질 때, 모든 노드를 방향성을 지켜 나열하는 것을 의미합니다. 이때, 그래프 내에 사이클(Cycle)이 존재하면 위상 정렬은 불가능합니다.

 

코딩 테스트에서의 위상 정렬 문제 해결 전략

 

1. 진입 차수(In-degree) 활용: 각 노드마다 진입 차수(In-degree)를 계산하여 해당 값이 0인 시작점부터 탐색을 시작합니다. 진입 차수란 특정한 노드로 들어오는 간선(Edge)의 수를 의미합니다. 탐색 과정에서 현재 노드와 연결된 간선을 제거하고 연결된 노드들의 진입 차수 값을 업데이트합니다. 모든 탐색이 완료되면 얻어진 순서가 바로 위상 정렬 결과입니다.
2. 깊이 우선 탐색(DFS): 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘을 사용하여 위상 정렬 문제를 해결할 수도 있습니다. DFS로 그래프를 탐색하며 현재 노드와 연결된 모든 자식(인접한)노드들을 재귀적으로 방문합니다. 방문한 순서대로 결과 리스트에 추가하면 위상 정렬 결과가 됩니다.
3. 큐(Queue): 큐(Queue) 자료구조를 활용하여 직접 구현할 수도 있습니다. 진입 차수(In-degree), 인접 리스트(Adjacency List), 큐(Queue), 결과 리스트 등 여러 변수와 자료구조가 필요하지만 구현하기엔 비교적 간단합니다. 각 단계별로 진입 차수가 0인 모든 노드들을 큐에 넣고 큐에서 하나씩 꺼내어 연결된 간선 제거 및 집계 과정을 반복하여 최종 결과 리스트를 얻습니다.

 

2056번: 작업

 

  문제  

 

• 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.
• 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)
• 모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

  해결 방법  

 

• 이 문제는 주어진 작업들과 그 작업들 간의 선행 관계가 주어졌을 때, 모든 작업을 완료하는데 걸리는 최소 시간을 구하는 문제입니다.

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

def topology_sort():
    q = deque()

    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
            result[i] += time[i]

    while q:
        cur = q.popleft()
        for i in graph[cur]:
            result[i] = max(result[i], result[cur] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

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

for i in range(1, n+1):
    data = list(map(int, input().split()))
    time[i] = data[0]
    for j in data[2:]:
        indegree[i] += 1
        graph[j].append(i)

topology_sort()
print(max(result))

 

 

1516번: 게임 개발

 

  문제  

 

• 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.
• 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.
• 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

 

  해결 방법  

 

• 이 문제는 게임 개발 순서와 각 건물을 짓는데 필요한 시간이 주어졌을 때, 모든 건물을 완성하는 데 필요한 최소 시간을 구하는 문제입니다.

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

def topology_sort():
    q = deque()

    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
            result[i] += time[i]

    while q:
        cur = q.popleft()
        for i in graph[cur]:
            result[i] = max(result[i], result[cur] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

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

for i in range(1, n+1):
    data = list(map(int, input().split()))
    time[i] = data[0]
    for j in data[1:-1]:
        indegree[i] += 1
        graph[j].append(i)

topology_sort()
for i in range(1, n+1): print(result[i])

 

 

• 위의 두 문제 모두 '작업'과 '게임 개발'이라는 주제로 다르지만 그 기본적인 해결 방법은 동일합니다. 위상 정렬 알고리즘은 그래프 내에서 순서가 필요한 문제를 해결하는 데 매우 유용합니다.
• 마지막으로 이런 유형의 문제를 접했을 때에는 반드시 사이클(cycle)이 없다는 것과 진입 차수(in-degree)가 중요하다는 점들을 기억하셔야 합니다. 위상 정렬은 사이클이 없는 DAG(Directed Acyclic Graph)에만 적용 가능하며, 각 노드의 진입 차수를 활용하여 탐색의 시작점과 종료점을 결정합니다.