반응형 1시간20분1 [BaekJoon/백준] 1167번 C++ 어려웠다. bfs로 풀어나가긴 했는데 그게 전부가 아니였다. 일단 bfs의 depth 개념을 이용하는 문제이긴 한데, depth 그 자체는 아니고, 간선마다 길이가 다르므로 그 값을 이용해줘야한다. 처음에는 모든 노드에서 bfs를 구하여 코드를 만들었다. 당연히 상식적인 선에서 이렇게 구현하면 문제가 풀렸다. 예제들도 다 들어맞길래 정답인 줄 알았는데.. 시간초과가 떴다. 문제는 모든 노드에서 bfs를 해줬던 것이였다. 알아보니, 트리의 지름을 구할 때엔 각각의 노드마다 bfs를 전부 시도할 필요는 없고 단 두번으로 해결된다고 한다. 왜 두번인지 더 알아봤는데도, 왜 두번인지 모르겠다. 설명에서는, 임의의 노드에서 가장 큰 가중치를 가진 노드를 찾은 뒤에 (간선의 길이를 포함하여 가장 멀리 떨어진 노드).. 2021. 5. 16. 이전 1 다음 반응형
