[프로그래머스] 트리 트리오 중간값

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

프로그래머스

🤔 문제분석

트리의 성질과 중간값의 성질을 이용하여 해결하는 문제이다.

간선이 단 1개 연결되어있는 노드에서 다른 노드 까지의 거리를 구하면 반드시 최대값을 갖는다. ( 트리의 성질 )

간선이 단 1개 연결되어있는 노드를 찾기위해서는 특정 아무 노드에서 다른 노드까지의 최대 거리 값을 가지고 있는 노드가 간선이 단 1개 연결되어있는 노드이다.

1. 특정 노드에서 간선이 1개인 특정노드를 구한다.
2. 간선이 1개인 노드에서 다른노드까지의 최대거리를 구한다.
3. 최대거리가 같은 노드가 여러개일경우 최대거리를 리턴하면 된다. 최대거리가 같은 노드가 1개일경우 최대거리-1 거리값을 리턴하면 된다. ( 중간값의 성질 )

💻 코드

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

import sys
from collections import deque
def solution(n, edges):
    new_edge = [[] for _ in range(n+1)]
    for a, b in edges:
        new_edge[a].append(b)
        new_edge[b].append(a)
        
    def bfs(start):
        distance = []
        queue = deque()
        queue.append((start, 0))
        visited = {start : 1}
        
        while queue:
            node, cost = queue.popleft()
            distance.append((node, cost))
            
            for child in new_edge[node]:
                if child not in visited:
                    visited[child] = 1
                    new_cost = cost + 1
                    queue.append((child, new_cost))

        return distance
    
    check = bfs(1)
    end = bfs(check[-1][0])
    
    if check[-1][1] == check[-2][1]:
        return end[-1][1]
    else:
        return end[-2][1]