백준 1968
-
백준 1967 트리의 지름Algorithm/BOJ 2021. 1. 21. 15:14
출처: https://www.acmicpc.net/problem/1967 분류: 트리 접근방식 문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다. root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면 leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다. root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :) 해결방법 dfs를 돌려서 루트에서 가장 먼 노드를 찾고, 그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다. 그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다. 트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢 im..