Algorithm in A..Z - Programmers 트리 트리오 중간값

https://programmers.co.kr/learn/courses/30/lessons/68937

코딩테스트 연습 - 트리 트리오 중간값

---

접근

1. 트리의 지름을 구할 수 있는 임의의 정점을 찾고 해당 정점과 다른 정점들 사이의 거리 중 2번째로 큰 값을 반환했다.

=> 12번 테스트 케이스에서 오답.

 

1번의 반례

위와 같은 그래프는 A-B를 통해 트리의 지금을 구할 수 있다. 해당 경우 A와 다른 정점들 사이의 거리 중 2번째로 큰 값을 반환한 값보다 (A, B, C)의 중간값이 더 크다.

=> 트리의 지름을 d라고 할 때 정점들 사이의 거리 중 d가 2개 이상 나올 수 있는 경우를 놓쳤기 때문에 1번 풀이법은 옳지 않다.

 

2. 트리의 지름을 구할수 있는 임의의 정점 A, B가 있을 때 1번은 A하나만 확인해서 오답이였다. A와 B 둘다 확인

=> 성공

---

코드

import com.sun.source.tree.ArrayAccessTree
import java.util.*
import kotlin.collections.ArrayList

class Solution {
    fun solution(n: Int, edges: Array<IntArray>): Int {
        val map = Array<ArrayList<Int>>(n + 1) { ArrayList() }
        edges.forEach {
            map[it.first()].add(it.last())
            map[it.last()].add(it.first())
        }

        val phase1 = map.bfs(1)
        val phase2 = map.bfs(phase1.first)
        if (phase2.second >= 2) {
            return phase2.third[phase2.first]
        }

        val phase3 = map.bfs(phase2.first)
        return if (phase3.second >= 2) {
            phase3.third[phase3.first]
        } else {
            phase3.third[phase3.first] - 1
        }
    }

    fun Array<ArrayList<Int>>.bfs(n: Int): Triple<Int, Int, IntArray> {
        val queue = LinkedList<Int>()
        val distance = IntArray(size) { -1 }

        queue.add(n)
        distance[n] = 0
        while (queue.isNotEmpty()) {
            val now = queue.poll()
            for (next in get(now)) {
                if (distance[next] == -1) {
                    queue.add(next)
                    distance[next] = distance[now] + 1
                }
            }
        }

        var index = 0
        for (i in 1 until distance.size) {
            if (distance[index] < distance[i]) {
                index = i
            }
        }

        return Triple(index, distance.count { it == distance[index] }, distance)
    }
}