스위프트 코딩테스트 강좌, 위상 정렬

코딩 테스트는 많은 소프트웨어 개발자에게 중요한 시험입니다. 특히, 알고리즘 문제를 해결하는 능력은 면접관이 지원자의 문제 해결 능력을 평가하는 데 중요한 요소가 됩니다. 이 강좌에서는 ‘위상 정렬’이라는 알고리즘의 본질과 적용 방법을 다룹니다. 위상 정렬은 주로 그래프 이론에서 사용되는 개념으로, 방향 그래프의 정점들을 선형으로 정렬하는 방법입니다.

1. 위상 정렬의 개념

위상 정렬은 Directed Acyclic Graph (DAG)에서 각 정점을 순서대로 나열하는 과정입니다. 이때, 한 정점이 다른 정점보다 먼저 나올 수 있는 조건은 간선의 방향이 결정합니다. 즉, 정점 A가 정점 B로 가는 간선이 있을 경우, 위상 정렬에서는 정점 A가 정점 B보다 먼저 나와야 합니다.

2. 문제 설명

문제: 주어진 강의와 선수 과목의 관계를 바탕으로 모든 강의를 종료하기 위한 선행 과목의 순서를 출력하는 프로그램을 작성하세요.

입력 형식

– 첫 번째 줄에는 정수 N (1 ≤ N ≤ 10^6)과 정수 M (1 ≤ M ≤ 10^6)이 주어지며, N은 강의의 수이고 M은 강의 간의 선수 과목 관계의 수입니다.

– 다음 M줄에는 두 정수 A와 B가 주어지며, A는 B의 선수 과목이라는 것을 의미합니다.

출력 형식

– 선수 과목을 만족하는 강의의 정렬된 순서를 한 줄에 출력합니다. 만약 이 과정을 수행할 수 없으면 0을 출력해야 합니다.

예제 입력

4 4
2 1
3 1
1 4
4 3

예제 출력

0

3. 문제 해결 접근법

이 문제는 위상 정렬 알고리즘을 통해 해결할 수 있습니다. 일반적으로 위상 정렬 알고리즘은 두 가지 방식으로 수행됩니다:

  • DFS(깊이 우선 탐색)을 이용한 방법
  • BFS(너비 우선 탐색) 및 진입 차수를 이용한 방법

4. BFS 기반 위상 정렬

BFS 방식의 위상 정렬을 통해 문제를 해결하는 방법을 살펴보겠습니다. 이 방법은 ‘진입 차수’를 계산하여, 진입 차수가 0인 정점들을 큐에 삽입합니다. 이후, 큐에서 하나씩 정점을 꺼내면서 그 정점에 연결된 다른 정점의 진입 차수를 감소시키는 방식으로 진행됩니다.

4.1. 알고리즘 단계

  1. 진입 차수를 저장하기 위한 배열을 생성합니다.
  2. 각 간선을 분석하면서, 진입 차수를 계산합니다.
  3. 진입 차수가 0인 정점을 큐에 삽입합니다.
  4. 큐에서 정점을 꺼내면서 관련된 정점의 진입 차수를 감소시킵니다.
  5. 모든 정점이 처리되었을 경우 결과를 반환하고, 처리되지 않은 정점이 있을 경우 0을 반환합니다.

5. 스위프트 구현

아래는 주어진 문제를 스위프트로 구현한 코드입니다.


import Foundation

func topologicalSort(N: Int, edges: [(Int, Int)]) {
    var graph = [[Int]](repeating: [Int](), count: N + 1)
    var inDegree = [Int](repeating: 0, count: N + 1)

    for edge in edges {
        let (a, b) = edge
        graph[a].append(b)
        inDegree[b] += 1
    }

    var result = [Int]()
    var queue = [Int]()

    // 진입 차수가 0인 정점을 큐에 삽입
    for i in 1...N {
        if inDegree[i] == 0 {
            queue.append(i)
        }
    }

    while !queue.isEmpty {
        let current = queue.removeFirst()
        result.append(current)

        for neighbor in graph[current] {
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0 {
                queue.append(neighbor)
            }
        }
    }

    if result.count == N {
        print(result.map { String($0) }.joined(separator: " "))
    } else {
        print(0)
    }
}

let N = 4
let M = 4
let edges = [(2, 1), (3, 1), (1, 4), (4, 3)]

topologicalSort(N: N, edges: edges)

6. 결론

위상 정렬은 많은 분야에서 사용되는 유용한 알고리즘입니다. 특히, 작업을 순차적으로 수행해야 할 때 선수 과목의 개념을 통해 강력한 도구로 활용됩니다. 이 문제를 통해 위상 정렬 알고리즘을 익히고, 다양한 문제에 적용할 수 있는 능력을 키우시길 바랍니다. 코딩 테스트에서는 이와 유사한 문제가 자주 출제되므로 충분한 연습이 필요합니다.