100년 뒤 개발자 한승규입니다.

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

원래 푸는 방법대로 풀지 않은 거 같다.

원래는 1번 노드에서 가장 먼 곳을 찾은 후, 그 노드에서 가장 먼 곳과의 거리를 구하면 된다.

그러면 노드에서는 지름을 구할 수 있다.

하지만 그냥 아무생각없이 모든 노드를 방문하는 방법으로 풀었는데, 그냥 풀렸다.

그래서 이번 문제는 그냥 간단하게 푸는 방법으로 풀도록 하겠다.

이번에는 그래프를 dict로 받았는데, 모든 노드에 대한 2차원 배열로 만들면 메모리 초과가 발생한다.

그냥 반복마다, 최대의 길이를 구하고 그 중에서 최대의 길이를 출력한다.

import sys
from collections import deque

n = int(sys.stdin.readline().strip())

node = {i: [] for i in range(n)}

for i in range(n - 1):
    start, end, weight = map(int, sys.stdin.readline().split())

    node[start - 1].append([end - 1, weight])
    node[end - 1].append([start - 1, weight])

result = 0

for i in range(n):
    cur_result = 0
    visited = [False for _ in range(n)]
    need_visit = deque()
    need_visit.append([0, i])
    visited[i] = True

    while need_visit:

        cur_weight, cur_node = need_visit.popleft()

        cur_result = max(cur_result, cur_weight)

        for next_node, next_weight in node[cur_node]:
            if visited[next_node] is False:
                visited[next_node] = True
                need_visit.append([cur_weight + next_weight, next_node])

    result = max(result, cur_result)

print(result)

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

트리의 지름을 구하는 방법은 우선, 한 노드에서 가장 멀리 있는 노드를 구한다.

그리고 그 노드에서 가장 멀리 있는 길이를 구한다.

그러면 그게 노드의 지름이 된다.

그러면 2번 길이를 구해야 하는 데, 귀찮아서 함수로 만들어버렸다.

우선 각 그래프에 대한 정보를 입력 받은 후 BFS를 진행한다.

처음의 BFS에서는 가장 멀리 있는 노드를 구하고, 그 다음의 BFS에서는 길이를 구한 후 출력한다.

from collections import deque
import sys

V = int(sys.stdin.readline())

graph = [[] for _ in range(V + 1)]

for _ in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for e in range(1, len(c) - 2, 2):
        graph[c[0]].append((c[e], c[e + 1]))


def bfs(target):
    weight = [-1] * (V + 1)
    weight[target] = 0
    need_visit = deque()
    need_visit.append(target)
    result = [0, 0]

    while need_visit:
        cur = need_visit.popleft()
        for v, w in graph[cur]:
            if weight[v] == -1:
                weight[v] = weight[cur] + w
                need_visit.append(v)
                if result[0] < weight[v]:
                    result = [weight[v], v]

    return result


print(bfs(bfs(1)[1])[0])