[Swift 알고리즘] 백준 BOJ - 1967 트리의 지름

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 1967 트리의 지름" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1967번: 트리의 지름

 

---

풀이

이번 문제는 트리 문제입니다.

트리에 대한 이해도가 있으면 좀 수월하게 해결할 수 있습니다.

 

저는 문제의 해결 방법은 쉽게 떠올랐는데 그걸 코드로 옮기는데 애를 좀 먹었습니다.

Swift가 아직도 많이 낯선가 봅니다...

 

1.

지름이 있기 위해서는 두 개의 노드가 필요합니다.

두 개의 노드 중 하나는 반드시 root node인 1에서 가장 깊은 depth를 가지고 있습니다.

따라서 dfs를 이용해 시작 노드에서 가장 긴 노드를 구합니다.

 

백준 예제의 경우 node 9로 root와의 거리가 28로 가장 깁니다.

 

2.

가장 긴 지름을 구성할 node를 하나 구했으니 다른 하나도 구해줘야 합니다.

다른 하나의 노드는 1번 과정에서 구한 node를 기준으로 가장 깊은 depth를 가지고 있어야 합니다.

즉, 1번에서 구한 node를 기준으로 dfs를 실행하면 됩니다.

 

1, 2번에 맞춰 코드를 작성하면 답을 구할 수 있을 것입니다.

한 가지 주의할 점은 node가 1개일 때도 input으로 들어온다는 점입니다.(100%에서 틀리는 경우)

이 때는 0을 출력하면 됩니다.

 

---

전체 코드

//1967 트리의 지름
import Foundation

let count = Int(readLine()!)!

if count == 1 {
    print(0)
} else {
    var graph: [Int: [(n: Int, len: Int)]] = [:]
    for i in 1...count {
        graph.updateValue([], forKey: i)
    }
    
    for _ in 0..<(count-1) {
        let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
        graph[input[0]]!.append((input[1], input[2]))
        graph[input[1]]!.append((input[0], input[2]))
    }
    
    var visited: [Bool] = Array(repeating: false, count: count + 1)
    var maxNode = 0
    var maxLength = 0
    func dfs(_ node: Int, _ depth: Int) {
        visited[node] = true
        
        if maxLength < depth {
            maxLength = depth
            maxNode = node
        }
        
        for node in graph[node]! {
            if !visited[node.n] {
                dfs(node.n, depth + node.len)
            }
        }
    }
    
    dfs(1, 0)
    
    maxLength = 0
    visited = Array(repeating: false, count: count + 1)
    
    dfs(maxNode, 0)
    
    print(maxLength)
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.