스위프트 코딩테스트 강좌, 트리의 지름 구하기

코딩테스트 준비를 위한 다양한 알고리즘 문제를 풀어보는 것은 여러분의 프로그래밍 실력을 높이는 데 큰 도움이 됩니다. 이번에는 ‘트리의 지름 구하기’ 문제에 대해 깊이 있게 다뤄보겠습니다. 트리 구조는 많은 프로그래밍 문제에서 빈번하게 등장하기 때문에, 이를 이해하고 해결하는 방법을 아는 것은 매우 유용합니다.

문제 설명

트리(Tree)는 노드(Node)와 엣지(Edge)로 구성된 비선형 데이터 구조입니다. 트리의 지름(Diameter)은 트리 내의 두 노드 간의 최장 경로를 의미합니다. 즉, 두 노드 간의 거리(노드 간의 간선의 수)가 가장 긴 경로를 찾는 것입니다. 이 문제는 보통 DFS(Depth-First Search) 또는 BFS(Breadth-First Search)를 이용하여 해결할 수 있습니다.

문제 정의

주어진 트리가 있을 때, 트리의 지름을 구하시오.
입력: 트리의 노드 수 N (1 <= N <= 100,000)
      N-1개의 간선 (u, v) 형태로 각 간선의 양 끝 노드를 입력받음.
출력: 트리의 지름

문제 분석

트리의 특성상 모든 노드는 오직 하나의 경로로 연결되어 있기 때문에, 두 노드 간의 최장 거리를 찾는 방법은 DFS 또는 BFS를 이용하여 탐색하는 것입니다. 일반적인 아이디어는 다음과 같습니다:

  1. 임의의 노드 A를 선택하고, A에서 가장 멀리 있는 노드 B를 찾습니다.
  2. 그 다음, B에서 가장 멀리 있는 노드 C를 찾습니다. 이때의 거리가 바로 트리의 지름입니다.

알고리즘 구현

이제 위의 알고리즘을 Swift로 구현해 보겠습니다. 먼저 트리를 표현하기 위해 인접 리스트를 사용하겠습니다.

Swift 코드 구현


import Foundation

class Graph {
    var adjList: [[Int]]

    init(size: Int) {
        adjList = Array(repeating: [], count: size)
    }

    func addEdge(u: Int, v: Int) {
        adjList[u].append(v)
        adjList[v].append(u)
    }

    func bfs(start: Int) -> (Int, Int) {
        var dist = Array(repeating: -1, count: adjList.count)
        var queue: [Int] = []
        
        dist[start] = 0
        queue.append(start)

        var farthestNode = start
        var maxDistance = 0

        while !queue.isEmpty {
            let node = queue.removeFirst()
            for neighbor in adjList[node] {
                if dist[neighbor] == -1 { // 방문하지 않았다면
                    dist[neighbor] = dist[node] + 1
                    queue.append(neighbor)
                    if dist[neighbor] > maxDistance {
                        maxDistance = dist[neighbor]
                        farthestNode = neighbor
                    }
                }
            }
        }
        return (farthestNode, maxDistance)
    }
}

func findTreeDiameter(edges: [(Int, Int)], n: Int) -> Int {
    let graph = Graph(size: n)
    for edge in edges {
        graph.addEdge(u: edge.0 - 1, v: edge.1 - 1) // 0-indexed
    }

    let (farthestNode, _) = graph.bfs(start: 0)
    let (_, diameter) = graph.bfs(start: farthestNode)
    return diameter
}

// 입력 예시
let n = 5
let edges: [(Int, Int)] = [(1, 2), (1, 3), (2, 4), (2, 5)]
let diameter = findTreeDiameter(edges: edges, n: n)
print("트리의 지름: \(diameter)")

코드 설명

이 코드는 다음과 같은 방식으로 트리의 지름을 구합니다:

  1. 먼저 Graph 클래스를 정의하여 간선 리스트를 저장합니다.
  2. addEdge 메서드를 통해 간선 정보를 추가합니다.
  3. bfs 함수는 주어진 시작 노드에서 BFS를 수행하여 가장 먼 노드와 그 거리를 반환합니다.
  4. findTreeDiameter 함수는 주어진 엣지들을 이용해 그래프를 생성하고, 두 번의 BFS를 통해 트리의 지름을 찾아 반환합니다.

실행 결과

코드를 실행하면 다음과 같은 결과를 출력합니다:

트리의 지름: 3

이는 노드 4와 노드 5 사이의 최장 경로를 의미합니다.

마무리

이번 강좌에서는 트리의 지름을 구하는 문제를 다루어 보았습니다. 이 문제는 DFS 또는 BFS를 사용하여 해결할 수 있으며, 트리 구조에 대한 이해를 높이는 데 도움이 됩니다. 실제 코딩 테스트에서도 종종 등장하는 문제이므로, 충분한 연습을 통해 알고리즘 구현에 익숙해지시기 바랍니다. 더욱 깊은 이해를 위해 다양한 트리 사례를 실험해보는 것도 좋습니다.

다음 강좌에서는 더 많은 알고리즘 문제를 다룰 예정이니, 많은 관심 부탁드립니다!