title: "[프로그래머스] 트리 트리오 중간값 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/68937"
description: "프로그래머스 Level 4 문제 [트리 트리오 중간값]의 풀이를 정리합니다."

문제 설명 및 제한사항

문제 설명

n개의 점으로 이루어진 트리가 있습니다. 이때, 트리 상에서 다음과 같은 것들을 정의합니다.

• 어떤 두 점 사이의 거리는, 두 점을 잇는 경로 상 간선의 개수로 정의합니다.
• 임의의 3개의 점 a, b, c에 대한 함수 f(a, b, c)의 값을 a와 b 사이의 거리, b와 c 사이의 거리, c와 a 사이의 거리, 3개 값의 중간값으로 정의합니다.

트리의 정점의 개수 n과 트리의 간선을 나타내는 2차원 정수 배열 edges가 매개변수로 주어집니다. 주어진 트리에서 임의의 3개의 점을 뽑아 만들 수 있는 모든 f값 중에서, 제일 큰 값을 구해 return 하도록 solution 함수를 완성해주세요.

제한 사항

• n은 3 이상 250,000 이하입니다.
• edges의 행의 개수는 n-1 입니다.
  • edges의 각 행은 [v1, v2] 2개의 정수로 이루어져 있으며, 이는 v1번 정점과 v2번 정점 사이에 간선이 있음을 의미합니다.
  • v1, v2는 각각 1 이상 n 이하입니다.
  • v1, v2는 다른 수입니다.
  • 입력으로 주어지는 그래프는 항상 트리입니다.

아이디어 및 해결 방법

코드

from collections import defaultdict
import sys; sys.setrecursionlimit(1000000)

def dfs(u, A, d, visited):
    if all(v in visited for v in A[u]):
        return u, d, 1
    
    farthestnode, maxdepth, maxdepthcnt = None, -1, 0
    for v in A[u]:
        if v in visited:
            continue
            
        visited.add(v)
        node, depth, depthcnt = dfs(v, A, d+1, visited)
        if depth > maxdepth:
            farthestnode, maxdepth, maxdepthcnt = node, depth, depthcnt
        elif depth == maxdepth:
            maxdepthcnt += depthcnt
            
    return farthestnode, maxdepth, maxdepthcnt

def solution(n, edges):
    # 트리의 지름을 구해서 절반을 정답으로 제출해볼까?
    A = defaultdict(list)
    for u, v in edges:
        A[u].append(v)
        A[v].append(u)
        
    visited = set()
    visited.add(1)
    farthest, _, _ = dfs(1, A, 0, visited)
    
    visited = set()
    visited.add(farthest)
    farthest, diameter, cnt1 = dfs(farthest, A, 0, visited)
    
    visited = set()
    visited.add(farthest)
    farthest, diameter, cnt2 = dfs(farthest, A, 0, visited)
    
    if cnt1 == 1 and cnt2 == 1:
        return diameter - 1
    else:
        return diameter

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges