[JS] 트리 트리오 중간값

트리 구조의 특징을 활용하여 해결하였다!!

 

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

프로그래머스

 

 

문제를 잘 읽어보면 정답이 "트리에서의 최장거리" 혹은 "트리에서의 최장거리 - 1"임을 알 수 있다.

 

1. 최장 거리의 두 점을 A,B라고 두고 A와 B사이에서 A혹은 B와 가장 인접한 점을 C로 두면 중간값이 최장거리 -1이 된다.

2. 최장거리가 여러 경우로 나오는 경우 3개의 점이 서로 최장거리가 되므로 중간값이 최장거리로 만들 수 있다.

 

 

즉, 해당 문제는 "트리의 최장거리 구하기" 문제로 바뀐다. 트리 구조에서 최장거리를 구하는 방법은 생각보다 단순하다!

 

1. 임의의 노드(A)를 잡아서 가장 거리가 먼 노드(B)를 정한다.

2. (B)노드를 기준으로 가장 거리가 먼 노드(C)를 구한다.

3. B-C 사이의 거리가 최장거리가 된다. (여러개일 수 있다)

 

 

 

 

 

 

function solution(n, edges) {
    const tree = [...Array(n+1)].map(_=>[])
    for(const [s,e] of edges){
        tree[s].push(e)
        tree[e].push(s)
    }
    
    const getMaxInfo = (node) => {
        
        const visited = Array(n+1).fill(false)
        const stk = [[node,0]]
        const ret = {
            maxLen : 0,
            ary : []
        }
        
        while(stk.length){
            const [node,cnt] = stk.pop()
            visited[node] = true
            if(cnt > ret.maxLen){
                ret.maxLen = cnt
                ret.ary = [node]
            } else if (cnt === ret.maxLen) {
                ret.ary.push(node)
            }
            
            for(const nxNode of tree[node]){
                if(visited[nxNode]) continue
                stk.push([nxNode,cnt+1])
            }
        }
        return ret
    }
    
    const {ary} = getMaxInfo(1)
    
    const ret = getMaxInfo(ary[0])
    if(ary.length>1 || ret.ary.length>1) return ret.maxLen
    else return ret.maxLen-1
    
    
    
}