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

문제 설명 및 제한사항

문제 설명

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

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

제한 사항

아이디어 및 해결 방법

코드

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