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

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): Int { val map = Array>(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>.bfs(n: Int): Triple { val queue = LinkedList() 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) } }

반응형

from http://rkdxowhd98.tistory.com/201 by ccl(A) rewrite - 2021-09-08 11:01:24