[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1167번 _ 트리의 지름

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

[문제]

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

[입력]

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

[출력]

첫째 줄에 트리의 지름을 출력한다.

 

[아이디어]

1) 트리의 지름은, 임의의 정점으로부터 가장 먼 정점을 찾은 뒤 해당 정점을 기준으로 다시 가장 먼 지점까지의 거리를 찾으면 된다고 한다.

2) 트리를 그래프로 해석한다면, 노드 i에서 노드 j로 이동하는 방법은 유일하기 때문에, 어떤 경로를 택하냐 보다는 어떤 두 정점 사이가 가장 먼 것인가를 구하는 문제이다.

3) 2)의 이유로 최단 경로 문제가 아니지만 다익스트라로 해결이 가능하다. (유일한 경로 = 최단경로)

4) 노드 1을 기준으로 다익스트라를 사용하여 가장 먼 노드를 구하고, 해당 노드로부터 가장 멀리 있는 노드까지의 거리를 구한다.

 

# 백트래킹을 중단하지 못해 시간초과
from collections import deque
v = int(input())
g = [[] for _ in range(v+1)]
for _ in range(v):
    tmp = deque(map(int, input().split()))
    for i in range(1,len(tmp)-1,2):
        g[tmp[0]].append((tmp[i],tmp[i+1]))

def dfs(start,visit,g):
    global n, cnt
    visit = visit.copy()
    visit[start] = 1
#     print(start,n,visit, ans)
    for a,b in g[start]:
        if not visit[a]:
            visit[a] = 1; n+=b
            dfs(a,visit,g)
            if n>ans[-1]:
                ans.append(n)
            visit[a] = 0; n-=b
    return

visit = [0 for _ in range(v+1)]
answer = 0
for i in range(1,v+1):
    ans = [0]; n = 0; cnt = 0
    dfs(i,visit,g)
    mm = max(ans)
    if answer < mm:
        answer = mm
print(answer)

처음에는 백트래킹으로 풀 수 있지 않을까 했는데, 주어지는 정점이 너무 많기도 하고 불필요하게 원래 위치로 돌아오는 것을 해결할 수 없으며, 모든 정점에 대해 탐색한다는 단점이 있다.

 

from collections import deque
import heapq

v = int(input())
g = [[] for _ in range(v+1)]
dist = [0]*(v+1)
for _ in range(v):
    tmp = deque(map(int, input().split()))
    for i in range(1,len(tmp)-1,2):
        g[tmp[0]].append((tmp[i],tmp[i+1]))
        
def dijk(start,dist,g,visit):
    dist = dist.copy()
    visit = visit.copy()
    q = []
    heapq.heappush(q,(0,start))
    while q:
        d,now = heapq.heappop(q)
        if now not in visit:
            visit.add(now)
            for a,b in g[now]:
                cost = d+b
                if cost > dist[a] and a not in visit:
                    dist[a] = cost
                    heapq.heappush(q,(cost,a))
#     print(dist)
    return max(dist), dist.index(max(dist))

visit = set()
a1,b1 = dijk(1,dist,g,visit)
a2, _ = dijk(b1,dist,g,visit)
print(a2)

다익스트라로 해결하되, 이번에는 방문 여부를 set으로 관리하는 방법으로 해봤다.