[BOJ] 1967 : 트리의 지름 [그래프/트리](Python)

문제 링크

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

1967번: 트리의 지름

소스 코드

import sys
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    visited = [False] * (n+1)
    distance = [0] * (n+1)
    graph = [[] for _ in range(n+1)]

    for _ in range(n-1):
        parent, child, weight = map(int, sys.stdin.readline().strip().split())
        graph[parent].append((weight, child))
        graph[child].append((weight, parent))

    dfs(1, graph, visited, distance)

    v = max(range(1,n+1), key=lambda x: distance[x])

    visited = [False] * (n+1)
    distance = [0] * (n+1)

    dfs(v, graph, visited, distance)

    u = max(range(1,n+1), key=lambda x: distance[x])

    print(distance[u])

def dfs(x, graph, visited, distance):
    visited[x] = True

    for weight, nx in graph[x]:
        if not visited[nx]:
            distance[nx] = distance[x] + weight
            dfs(nx, graph, visited, distance)

if __name__ == '__main__':
    main()

 

해설

• 그래프, 트리, DFS

똑같은 로직으로 풀 수 있는 문제가 있어서 어제 트리의 지름 문제를 풀었는데 오늘도 풀게 되었습니다.

풀이 로직이 완전히 동일하고 입력 방식에만 차이가 있습니다.

따라서 해설을 작성하지는 않고 이전 게시물의 링크를 첨부하겠습니다.

 

오늘 얻은 교훈은..

1. 백준에서 파이썬으로 재귀 함수를 사용할 때는 setrecursionlimit 함수를 반드시 사용하자(^^..)

2. print문으로 디버깅했으면 반드시 지우자..(소중한 시간이 잔뜩 증발 🤬)

 

https://chanmuzi.tistory.com/199

[BOJ] 1167 : 트리의 지름 [그래프이론/트리](Python)