백준 2250 트리의 높이와 너비

출처: https://www.acmicpc.net/problem/2250

분류: 트리, 중위순회

---

접근방식

너비가 가장 큰 높이를 구해야하는 문제였습니다.

https://www.acmicpc.net/problem/2250

문제의 그림이 힌트를 주고 있는데요, 가장 왼쪽 노드부터 x가 하나씩 증가하고 있습니다.

중위 순회를 하면 "왼쪽 -> 루트 -> 오른쪽" 순서로 방문하기 때문에
이 순서가 곧 x가 1인 노드부터 차례대로 방문하는 순서입니다.

이 부분까지 이해가 됐다면 구현만 해주면 되는데요!

저는 그냥 중위순회에서 다 처리해버렸습니다.
전역적으로 사용하는 x값을 가지고 다니면서 노드에 넣었으면 1 증가시키는 방식으로 x를 처리했구요
해당 레벨의 최대, 최소 x값을 넣는 배열을 전역적으로 만들어 놓고 최대 최소를 업데이트 시켜줬습니다.

func markWhileInOrder(currentX: inout Int) {
    self.level = (parents?.level ?? 0) + 1
    if diffenceInLevel.count-1 < level {
        diffenceInLevel.append((n, 0))
    }
    
    leftChild?.markWhileInOrder(currentX: &currentX)
    self.x = currentX
    currentX += 1
    rightChild?.markWhileInOrder(currentX: &currentX)
    
    if x < diffenceInLevel[level].min {
        diffenceInLevel[level].min = x
    }
    if x > diffenceInLevel[level].max {
        diffenceInLevel[level].max = x
    }
}

 

해결방법

class Node {
    var parents: Node?
    var leftChild: Node?
    var rightChild: Node?
    var idx: Int
    var level = 0
    var x = 0
    
    init(_ idx: Int) {
        self.idx = idx
    }
    
    func markWhileInOrder(currentX: inout Int) {
        self.level = (parents?.level ?? 0) + 1
        if diffenceInLevel.count-1 < level {
            diffenceInLevel.append((n, 0))
        }
        
        leftChild?.markWhileInOrder(currentX: &currentX)
        self.x = currentX
        currentX += 1
        rightChild?.markWhileInOrder(currentX: &currentX)
        
        if x < diffenceInLevel[level].min {
            diffenceInLevel[level].min = x
        }
        if x > diffenceInLevel[level].max {
            diffenceInLevel[level].max = x
        }
    }
}

let n = Int(readLine()!)!
var tree = (0..<n).map { Node($0) }
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (idx, left, right) = (input[0]-1, input[1]-1, input[2]-1)
    
    if left >= 0 {
        tree[idx].leftChild = tree[left]
        tree[left].parents = tree[idx]
    }
    if right >= 0 {
        tree[idx].rightChild = tree[right]
        tree[right].parents = tree[idx]
    }
}

var diffenceInLevel: [(min: Int, max: Int)] = [(0, 0)]
let root = tree.filter({ $0.parents == nil })[0]
var currentX = 1
root.markWhileInOrder(currentX: &currentX)

var maxDiffLevel = 0
var maxDiff = 0
for level in 1..<diffenceInLevel.count {
    let diff = abs(diffenceInLevel[level].min - diffenceInLevel[level].max)+1
    if maxDiff < diff {
        maxDiff = diff
        maxDiffLevel = level
    }
}
print("\(maxDiffLevel) \(maxDiff)")