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

난이도 : 골드4

풀이일 : 2401184

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

1967번: 트리의 지름

---

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

---

1차 시도 오답

import sys
from collections import deque

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

    while queue:
        now = queue.popleft()

        for cost, next in load[now]:
            if not visited[next]:
                visited[next] = visited[now] + cost
                queue.append(next)

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

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

for _ in range(n-1):
    p, r, c = list(map(int, sys.stdin.readline().split()))
    load[p].append([c, r])
    load[r].append([c, p])

BFS(1)
print(BFS(start))

 

코드 구성

• BFS 방식으로 노드 1에서부터 가장 먼 노드를 찾아 해당 노드를 start로 재할당
• start에서 가장 먼 노드를 찾아 정답 출력

틀린 이유

• visited 배열을 0으로 초기화해둔 부분에서 문제 발생

---

2차 시도 정답

import sys
from collections import deque

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

    while queue:
        now = queue.popleft()

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

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

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

for _ in range(n-1):
    p, r, c = list(map(int, sys.stdin.readline().split()))
    load[p].append([c, r])
    load[r].append([c, p])

BFS(1)
print(BFS(start))

코드 변화

• visited 배열 초기화를 -1로 해두고 조건 수정

---

느낀점

• 다익스트라랑 트리로 아주 복잡하게 풀고 있느라 오래걸렸다.
• 문제를 좀 보고 알고리즘을 생각하고 풀이를 시작하자