[Programmers] Q68937 트리 트리오 중간값

[Programmers] Q68937 트리 트리오 중간값

Question

Language: Python

해당 문제의 풀이는 해설을 참고 하였다.

우선, 노드가 최대 25만개이므로, 모든 조합을 다 고려할 수는 없는 점을 확인할 수 있다.

중간값

중간값의 정의에 따르면 아래와 같이 중간에 위치한 값을 의미한다.

[1,2,3] ==> 2

중간값이 위와 같은 특징을 가지고 있기 때문에 트리에서 정점간에 거리를 구했을 때, 최대 거리를 가지는 정점의 경우가 2개 이상인 경우, 자연스럽게 최대값이 중간값이 되며, 그렇지 않은 경우에는 최대값에서 1을 감한 숫자가 중간값이 된다.(모든 노드는 서로 연결되어 있기 때문에 최대 거리를 가지는 정점 바로 앞에 있는 노드까지의 거리가 중간값이 된다.)

1. 그러면 최대 거리를 구하기 위해 종단점을 구한다. 1번 노드를 루트 노드로 설정해서 가장 먼 거리에 있는 종단 노드를 구한다.

distances=bfs(1)
leaf=distances[-1][0]

1. 이후, 종단 점에 대해서 가장 먼 거리에 있는 노드를 구한다. 이때, 최대 거리를 가지는 노드가 2개 이상인 경우, 최대거리가 중간값이 된다.

#해당 종단점에서 가장 먼 거리에 있는 정점 구하기
distances=bfs(leaf)
if distances[-1][1]==distances[-2][1]:
    return distances[-1][1]

1. 만일 최대값이 유일한 경우, 최대 거리를 가지는 노드에 대해서 다시 한번 가장 먼 거리에 있는 노드를 구해본다(3번 과정을 역으로 해서 또 다른 최대거리가 발생할 수 있는 지 확인한다.). 만일 최대 거리를 가지는 노드가 2개 이상인 경우 최대 거리가 중간값이 되며, 최대 거리가 유일한 경우 최대거리에서 1을 감한 값이 중간값이 된다.

leaf2=distances[-1][0]
distances=bfs(leaf2)

if distances[-1][1]==distances[-2][1]:
    return distances[-1][1]

return distances[-1][1]-1

Solution

from collections import deque

def solution(n, edges):
    answer = 0

    graph=[[] for _ in range(n+1)]

    counts=[0]*(n+1)

    for v1,v2 in edges:
        graph[v1].append(v2)
        graph[v2].append(v1)
        counts[v1]+=1
        counts[v2]+=1

    end_points=[vertex for vertex in range(1,n+1) if counts[vertex]==1]

    def bfs(start_point):
        distances=[]
        queue=deque([(start_point,0)])

        visited=[False]*(n+1)

        while queue:
            vertex,count= queue.popleft()

            if visited[vertex]:
                continue
            visited[vertex]=True
            distances.append((vertex,count))
            for adj_vertex in graph[vertex]:
                queue.append((adj_vertex,count+1))

        return distances


    #임의 종단점 구해서
    distances=bfs(1)
    leaf=distances[-1][0]
    
    #해당 종단점에서 가장 먼 거리에 있는 정점 구하기
    distances=bfs(leaf)
    
    #최대 길이가 2개 이상인 경우
    if distances[-1][1]==distances[-2][1]:
        return distances[-1][1]
    
    #그렇기 않은 경우 가장 먼 거리에 있는 정점에서 다시 한번 순회 수행해서 최대길이를 구해준다.
    leaf2=distances[-1][0]
    distances=bfs(leaf2)
    #최대 길이가 2개 이상인 경우
    if distances[-1][1]==distances[-2][1]:
        return distances[-1][1]

    return distances[-1][1]-1