반응형
SMALL
트리의 지름 파이썬
-
백준 1167번 트리의 지름 (Gold 2)알고리즘 2023. 7. 26. 14:59
트리에서 임의의 두 점 사이의 거리가 가장 긴 경우를 지름이라고 할 때, 이 지름을 구하는 문제입니다. 시도 1. 첫 노드부터 마지막 노드까지 순회를 하면서 가장 거리가 먼 노드를 구하고 해당 길이 중 최대 길이를 출력하도록 했습니다. 각 노드로부터의 거리를 저장하기 위한 변수 dp와 각 순회마다 노드의 방문 여부를 확인하는 visited배열도 선언해주었습니다. dp 배열과 visited 배열은 2차 배열로 선언했습니다. dp[i][j]일 경우 i 노드에서 j 노드로 가는 가장 긴 경로를 저장하고 visited[i][j]일 경우 i 노드에서 하나의 간선으로 j를 갈 수 있을 경우 i->j 로 갔었는지 여부를 저장하도록 해주었습니다. 이 후 priorityqueue를 이용해 현재까지 이동 거리가 긴 경우부..