문제 설명 및 제한사항
문제 설명
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
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges