백준 1167 트리의 지름 파이썬 풀이

난이도 : 골드2

풀이일 : 2401206

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

1167번: 트리의 지름

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys
from collections import deque

def BFS(n):
    global start
    visited = [-1 for _ in range(V + 1)]
    queue = deque([n])
    visited[n] = 0

    while queue:
        now = queue.popleft()

        for cost, next in tree[now]:
            if visited[next] < 0:
                visited[next] = visited[now] + cost
                queue.append(next)

    start = visited.index(max(visited))
    return max(visited)


V = int(sys.stdin.readline())
tree = [[] for _ in range(V + 1)]
start = 0

for _ in range(V):
    temp = list(map(int, sys.stdin.readline().split()))
    start = temp[0]
    for i in range(1, len(temp)-1):
        if i % 2:
            tree[temp[0]].append([temp[i+1], temp[i]])

BFS(1)
print(BFS(start))

 

• BFS 탐색으로 임의의 출발점 1에서 가장 먼 정점까지의 거리 탐색
• 가장 거리가 먼 정점을 start로 설정
• start에서 다시 BFS 탐색으로 가장 먼 정점까지의 거리 탐색 및 출력

---

느낀점

• 입력을 받는 과정이 조금 까다로워서 골드2 문제인가 생각했다. 연결된 모든 정점 정보가 주어져서 파이썬으로는 별로 어려웠던것 같지 않은데, 나중에 자바로 풀어봐야지.
• 얼마 전에 풀었던 비슷한 문제 덕분에 오늘은 조금 날로먹는 하루가 되었다. 깔끔하게 풀어서 기분 좋으니까 사진도 남겨둬야지.