[python] 백준 1967 트리의 지름

1967번: 트리의 지름 (acmicpc.net)

1967번: 트리의 지름

노드사이의 가장 먼 거리를 구하면 되는 문제

 

BFS

 

bfs를 사용해서 가장 멀리 떨어진 노드와 거리를 구함

처음에는 모든 노드를 출발점으로 잡고 bfs를 돌렸는데 시간이 오래 걸림

=> (임의의 노드에서 가장 멀리 떨어진 노드)에서 가장 멀리 떨어진 노드까지의 거리가 가장 트리의 지름이 된다.

(참고) 트리의 지름 구하기 (myungwoo.kr)

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

def bfs(s):
    global max_v #가장 먼 노드 저장 (처음 bfs에서만 사용)
    max_v=1 #1번 노드부터 시작했기 때문에 우선 1로 초기화
    sum=0 #최고 이동거리
    visited=[False]*(N+1) #방문처리

    que=deque()
    que.append((s,0)) #시작 노드 큐에 담아주기
    visited[s]=True #방문처리
    
    while(que): #큐가 비어있지 않을 때까지
        v,e = que.pop()
        if e>sum: #만약 이동거리가 지금까지 이동거리보다 멀다면
            sum=e #sum 갱신
            max_v=v #가장 먼 노드 갱신

        for next in adj[v]: #인접된 노드 방문
            if(visited[next[0]]): continue #만약 방문했다면 넘어가기
            visited[next[0]]=True #방문처리
            que.append((next[0],e+next[1])) #큐에 다음 노드와 지금까지 이동거리 넣어주기
    return sum #최대 이동거리 반환


N = int(input())

adj=[[] for _ in range(N+1)] #연결 노드 저장 리스트


for i in range(N-1):
    f,t,v=map(int,input().split())
    adj[f].append([t,v]) #양방향으로 담아주기
    adj[t].append([f,v])

bfs(1) #아무 노드나 상관 없음 => 임의의 노드에서 가장 먼 노드 구하기 (max_v)

print(bfs(max_v)) #가장 먼 노드에서 가장 먼 노드까지의 이동거리 출력

 

 

 

플로이드 와샬

비록 메모리초과때문에 플로이드 와샬로 푸는 건 불가능하지만

n이 작다면 가능할 테니까..

n = int(input())
adj=[[1e7]*(n+1) for _ in range(n+1)]

for i in range(n-1):
    f,e,v=map(int,input().split())
    adj[f][e]=v
    adj[e][f]=v

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])

result=0
for i in range(1,n+1):
    for j in range(1,n+1):
        result=max(result, adj[i][j])
print(result)