[Python]백준 1167 트리의 지름

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

1167번: 트리의 지름

 

문제 해결

- graph 리스트를 통해 연결되어있는 점들의 정보를 저장한다.

- visited[i] = value : 1점에서 i점까지 거리가 value인 것을 나타낸다.

- 어느 점에서 시작하든 반대쪽 리프(맨 밑에 있는점)까지가 가장 멀기 때문에 한 점에서 가장 멀리 떨어져 있는 점을 구한다. visited.index(max(visited))를 통해 구한다.

- 1점에서 반대쪽 리프의 인덱스를 구했으므로 거기서 반대쪽 리프의 인덱스까지가 이 트리에서 가장 먼 거리일 것이다.

- 1점에서 반대쪽 리프에서 시작하는 DFS 함수를 작동해 가장 먼 거리에 있는 인덱스까지 거리를 구할 수 있다.

- 사실 같은 논리로 BFS함수를 이용해서도 풀 수 있다.

코드(DFS)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(x,y):
    for a, b in graph[x]:
        if visited[a] == -1:
            visited[a] = b+y
            dfs(a,b+y)
v = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(v):
    T = list(map(int, input().split()))
    for i in range(1,len(T)-1,2):
        graph[T[0]].append([T[i], T[i+1]])
visited = [-1 for _ in range(v+1)]
visited[1] = 0
dfs(1,0)
start = visited.index(max(visited))
new_visited= [-1 for _ in range(v+1)]
new_visited[start]=0
dfs(start,0)
print(max(new_visited))

코드(BFS)

import sys
input = sys.stdin.readline
from collections import deque

def bfs(start):
    visited = [-1 for _ in range(v+1)]
    que = deque()
    que.append(start)
    visited[start] = 0
    maximum = [0, 0]
    while que:
        t = que.popleft()
        for e, w in graph[t]:
            if visited[e] == -1:
                visited[e] = visited[t] + w
                que.append(e)
                if maximum[0] < visited[e]:
                    maximum = visited[e], e
    return maximum
v = int(input())
graph = [[] for _ in range(v+1)]

for _ in range(v):
    T = list(map(int, input().split()))
    for i in range(1,len(T)-1, 2):
        graph[T[0]].append((T[i], T[i+1]))
distance, node = bfs(1)
distance, node = bfs(node)
print(distance)