백준 1167번 트리의 지름 (Gold 2)

트리에서 임의의 두 점 사이의 거리가 가장 긴 경우를 지름이라고 할 때, 이 지름을 구하는 문제입니다.

 

시도 1.

첫 노드부터 마지막 노드까지 순회를 하면서 가장 거리가 먼 노드를 구하고 해당 길이 중 최대 길이를 출력하도록 했습니다.

각 노드로부터의 거리를 저장하기 위한 변수 dp와 각 순회마다 노드의 방문 여부를 확인하는 visited배열도 선언해주었습니다.

dp 배열과 visited 배열은 2차 배열로 선언했습니다.

dp[i][j]일 경우 i 노드에서 j 노드로 가는 가장 긴 경로를 저장하고

visited[i][j]일 경우 i 노드에서 하나의 간선으로 j를 갈 수 있을 경우 i->j 로 갔었는지 여부를 저장하도록 해주었습니다.

 

이 후 priorityqueue를 이용해 현재까지 이동 거리가 긴 경우부터 pop되어 거리가 먼 노드를 먼저 찾을 수 있도록 해주었습니다.

그리고 현재까지 이동거리와 현재까지 가장 긴 거리를 비교하여 가장 긴 거리를 업데이트해주도록 해주었습니다.

dp=[[0 for __ in range(V+1)] for _ in range(V+1)]

for i in range(1,V+1):
    visited = [[False for __ in range(V+1)] for _ in range(V+1)]
    queue = PriorityQueue()
    queue.put((0,0,i))
    
    while not queue.empty():
        temp,distance,node = queue.get()
        
        maxDistance = max(maxDistance,distance)
        
        if distance<dp[i][node]:
            continue
        
        for j in range(0,len(edges[node]),2):
            nowNode,nowDistance=edges[node][j],edges[node][j+1]
            newDistance = nowDistance+distance
            
            if visited[node][nowNode]:
                continue
            
            visited[node][nowNode]=True
            visited[nowNode][node]=True
            if newDistance>dp[i][node]:
                dp[i][node]=newDistance
                dp[node][i]=newDistance
                queue.put((-newDistance,newDistance,nowNode))

코드의 결과는.... 메모리 초과였습니다. 아무래도 V의 개수가 100,000개이기도 하고 visited를 V번 계속 선언을 해주다보니 메모리초과가 나게 된 것 같습니다.

여기서 메모리를 줄이기 위한 노력을 했지만, 최대 거리를 찾기 위해 visited라는 배열을 선언하는 것은 필수적이라고 생각했기 때문에 아예 다른 접근 방법이 필요할 것이라고 생각했습니다.

 

 

시도 2.

증명 1.

가장 먼 거리를 구하는 방법에 대해 고민해 보았습니다.

트리의 구조로 생각해 볼 때, 최대 길이를 가질 수 있는 조건은 leaf 노드에서 다른 leaf노드로 이동하면 될 것이라고 생각했습니다.

그림 1

위와 같은 예시를 들어보도록 하겠습니다. 12, 14를 잇는 간선을 포함하는 것이 최대가 될 것이라고 보입니다. 하지만, 12와 14만 잇는다고 최대 길이가 될 수 없습니다. 12, 14 간선을 포함한 1번 3번 5번 노드를 이은 뒤,  2번 4번 노드, 8번 노드까지 이은 길이가 최대 길이가 될 것입니다. 다음 간선으로 진행 할 수 없는 노드까지 가야지만 최대 길이가 됩니다. 이처럼 리프 노드를 포함하지 않고서는 최대의 길이를 완성 시킬 수 없습니다.

(여기서 리프 노드는 이어진 간선의 길이가 1개인 노드를 말합니다.)

 

증명 2.

그렇다면 최대 길이로 하는 leaf 노드 두 개를 어떻게 찾을 것인지 생각해보았습니다.

트리에서 두 개의 leaf노드를 잇는 노드 중 아무 노드나 루트 노드가 될 수 있습니다.

그림 2

위의 그림 1에서 리프 노드 4, 8을 잇는 노드 중 한 노드를 루트노드로 바꾼 경우입니다. 문제에서 어떤 종류의 트리인지 정의해주지 않았으므로 위와 같은 트리로 정의될 수도 있습니다.

 

증명 3.

그리고, 어떤 노드를 루트 노드라고 할 때 가장 먼 리프 노드를 구한다면 트리 지름에 포함된 간선들의 부분 집합이 항상 포함 될 것 입니다. 트리 지름에 포함된 간선들은 어떤 간선들의 합보다 항상 커야되기 때문입니다. 그래서, 어떤 노드에서든지 해당 노드에서 가장 먼 거리의 리프 노드를 찾을 경우 트리 지름에 포함된 리프 노드 중 하나의 리프 노드를 구할 수 있을 것이라고 생각했습니다.

그림 1

그림 1은 트리 지름에 포함된 노드를 루트 노드로 두었을 경우입니다. 1번 노드에서 가장 먼 리프 노드는 8번 노드입니다.  8번 노드는 트리 지름에 포함된 리프 노드입니다.

그림 3

그림 3은 트리 지름에 포함되지 않은 6번 노드를 루트 노드로 두었을 경우입니다. 6번 노드에서 가장 멀리 떨어진 리프 노드를 찾아보도록 하겠습니다.

가장 멀리 떨어진 노드는 4로 트리 지름에 포함된 리프 노드임을 알 수 있습니다.

 

다른 접점들을 예로 들어도 똑같이 트리 지름에 포함된 리프 노드를 찾을 수 있다는 것을 알 수 있습니다.

 

만약의 경우도 생각해본다면, 그림 1에서 만약 1번 노드에서 4번 노드로 가는 간선의 합이 가장 크다면 어떡하지? 혹은, 그림 3에서 7번 노드 밑에 더 많은 노드가 존재해서, 7번 노드 밑의 어떤 노드가 가장 먼 노드가 된다면 어떡하지? 라고 고민을 많이 했던 것 같습니다.

위와 같은 생각이 들었다면, 그 예외가 되는 리프노드가 애초에 트리 지름에 포함된 리프 노드였을 것이다라는 것을 캐치해야합니다.

저와 같은 경우 이럴 경우는 예외가 되지 않을까?라는 생각을 많이 하는데, 위와 같이 바로 증명적인 생각을 하는데 오래걸려서 이번 문제도 오래 걸리게 되었습니다...

 

해결

이 후 해당 리프 노드로부터 다른 쪽 리프 노드를 dfs를 통해 구하면 트리의 지름을 구할 수 있을 것이라고 생각했습니다.

위에서 보인 것과 같이 한 접점으로부터 가장 멀리 떨어진 리프 노드를 구했을 경우, 해당 리프노드로부터 가장 멀리 떨어진 리프노드를 구한다면 해당 길이가 트리의 지름에 해당됩니다.

def dfs(node, distance):
    for nowNode, nowDistance in graph[node]:
        if dp[nowNode] == -1:
            dp[nowNode] = nowDistance + distance 
            dfs(nowNode, nowDistance + distance)

dp = [-1 for _ in range(V+1)]
dp[1]=0
dfs(1,0)
longestNode=dp.index(max(dp))

dp = [-1 for _ in range(V+1)]
dp[longestNode]=0
dfs(longestNode,0)
print(max(dp))

(입력 및 변수 선언 부분은 생략됐습니다.)

 

 

 

이번 문제는 해결 방법에 대해 고민하는데 오래 걸리게 되었습니다. 예외적인 부분에 대해서 확실하게 잡을 수 있도록 증명하는 태도를 가지는 것이 필요한 것 같습니다.