파이썬 코딩테스트 강좌, 위상 정렬

위상 정렬(Topological Sorting)은 Directed Acyclic Graph (DAG, 방향성이 있는 비순환 그래프)에서 노드들을 정렬하는 방법입니다. 모든 간선이 위의 노드에서 아래의 노드로 향하는 순서로 배열 하는 것입니다. 이 정렬은 주로 작업의 수행 순서나, dependency(의존성) 및 다양한 프로그래밍 문제에서 사용됩니다.

문제 설명

주어진 수업 개수 N과 각 수업 간의 선후 관계를 나타내는 edges 리스트가 있습니다. 수업을 들을 수 있는 순서를 위상 정렬 알고리즘을 사용하여 구하는 문제입니다.

입력 형식

N = 6
edges = [(2, 1), (3, 1), (4, 1), (6, 4), (5, 2), (5, 3)]

출력 형식

1 2 3 4 5 6 (수업을 들을 수 있는 한 가지 순서)

문제 풀이 과정

1. 문제 이해하기

위상 정렬 문제는 주어진 노드들(N)과 간선 정보(edges)를 통해 선후 관계를 정립한 후, 모든 노드를 정렬하는 것입니다. 여기서 edges는 (A, B) 형태로 표현되며, A를 먼저 들어야 B를 들을 수 있음을 의미합니다.

2. 입력 파라미터 처리

위상 정렬을 구현하기 위해 우선 그래프의 인접리스트 및 진입 차수 배열을 구성해야 합니다. 진입 차수 배열은 각 노드가 들어야 할 수업의 수를 카운트합니다.

from collections import deque

def topological_sort(N, edges):
    # 그래프와 진입차수 초기화
    graph = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    # 간선 정보를 그래프와 진입차수에 등록
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

3. 위상 정렬 알고리즘 설계

이제, 위상 정렬을 수행하기 위한 알고리즘을 설계하겠습니다. 진입 차수가 0인 노드를 큐(Queue)에 추가하고, 큐에서 노드를 하나씩 꺼내면서 그 노드와 연결된 다른 노드들의 진입 차수를 감소시킵니다. 감소 후 진입 차수가 0이 되는 노드는 다시 큐에 추가됩니다. 이 과정을 큐가 빌 때까지 반복합니다. 최종적으로는 정렬된 노드의 순서를 반환합니다.

    # 진입차수가 0인 노드를 큐에 추가
    queue = deque()
    for i in range(1, N + 1):
        if in_degree[i] == 0:
            queue.append(i)

    result = []
    
    while queue:
        current = queue.popleft()
        result.append(current)
        
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result

4. 전체 코드 작성 및 실행

이제 전체 코드를 통합하여 최종 코드를 작성하겠습니다. 처리한 입력값을 함수에 전달하여 결과를 확인할 수 있습니다.

N = 6
edges = [(2, 1), (3, 1), (4, 1), (6, 4), (5, 2), (5, 3)]

sorted_order = topological_sort(N, edges)
print("수업을 들을 수 있는 순서:", sorted_order)

5. 결과 및 평가

위 코드를 실행하면 위상 정렬을 통해 수업을 들을 수 있는 순서를 구할 수 있습니다. 이 과정에서 그래프의 성질에 따라 여러 개의 올바른 정답이 나올 수 있습니다. 따라서 알고리즘이 올바르게 작동했다면 결과의 유효성을 폭넓게 검증할 필요가 있습니다.

6. 코드 및 알고리즘 최적화

위상 정렬 알고리즘의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점(vertex)의 수, E는 간선(edge)의 수입니다. 이 알고리즘은 대규모 데이터셋에서도 효율적으로 동작할 수 있기 때문에 취업 코딩테스트에 유용한 도구가 될 수 있습니다.

결론

위상 정렬은 그래프 이론에서 유용하게 사용되는 알고리즘으로, 다양한 문제에 응용될 수 있습니다. 이번 강좌에서는 파이썬을 이용해 위상 정렬을 구현해보았고, 실전 코딩테스트에 적합한 내용을 제공하였습니다. 앞으로도 이러한 알고리즘 문제를 깊이 있게 이해하고 활용하시길 바랍니다.