MZ 개발자

이 문제는 이전에 풀었던 문제와 입력 방식만 다른 완전히 같은 문제이다. https://devconf.tistory.com/40 BOJ 1967 트리의 지름 문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드 devconf.tistory.com 기본적인 방식은 특정 아무 위치에서 DFS를 통해 길이가 최대가 되는 시작점을 구하고, 그 시작점에서 다시한번 DFS를 돌리면 된다. #include #include #include #include using namespace std; int v; vector adj[100001]; bool visited[100001]; int ..

문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드에서 가장 깊이 들어가야 최소한 최대 길이가 될것 같다는 생각을 하였다. DFS를 생각한것이다. 하지만 DFS 한번만으로 도저히 답을 찾아낼 수 없었다. 풀이를 보니 DFS를 두번 사용 해야 한다고 하였다. 왜 DFS를 두번 사용해야 하는지 이해가 안되다가 다음과 같은 특징을 이해한 다음에 문제를 해결할 수 있었다. 하나의 정점에서 가장 멀리 있는 정점은 원의 지름 부분에 해당하는 정점이다. 즉 어느 점에서 DFS를 통해 가장 긴 점을 찾으면 그 점은 가장 지름이 긴 원의 시작 점이 된다. 이후 그 시작점에서 또 가장 긴..