(Python) - BOJ(1167번) : 트리의 지름

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

1167번: 트리의 지름

---

• 해설 : 

트리의 노드와 간선정보가 주어질 때, 임의의 두 노드사이의 최대거리를 구하는 문제이다.

 

 

 

---

• 풀이 :

BFS의 구현은 쉬웠지만 답을 도출하는 아이디어를 떠올리기 힘든 문제였다.

 

1. 루트노드에서 BFS로 탐색하여 가장 멀리 떨어진 노드를 찾는다.

2. 루트로부터 가장 멀리 떨어진 노드로부터 가장 멀리 떨어진 노드를 찾는다.

 

BFS를 총 2회 실행해야 찾을 수 있는 문제였다.

 

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
 
def bfs(start):
    queue = deque([start])
    length = [-1 for _ in range(V+1)]
    length[start] = 0
    while queue:
        s = queue.popleft()
        for k,m in rel[s]:
            if length[k] == -1:
                queue.append(k)
                length[k] = max(length[s]+m,length[k])
    #print(length)
    z = max(length)
    return [length.index(z),z]
 
if __name__ == "__main__":
    V = int(sys.stdin.readline())
    rel = [[] for _ in range(V+1)]
    for _ in range(V):
        check = list(map(int,sys.stdin.readline().split()))
        i = 1
        #print(check)
        while check[i] != -1:# or check[i] != '\n':
            rel[check[0]].append([check[i],check[i+1]])
            i+=2
    answer = 0
    #for i in range(1,V+1):
        #answer = max(answer,dfs(i))
    print(bfs(bfs(1)[0])[1])