깊이_우선_탐색

[C++] 백준 1167번 트리의 지름

[C++] 백준 1967번 트리의 지름 그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다 kimyunseok.tistory.com 위 문제와 거의 똑같은 문제. 차이점이라면, 루트 노드가 1이 아니다. 정점 번호가 작은 순서부터 입력되는 것이 아니라 랜덤으로 입력된다. -1이 나오기 전까지 노드를 연결시킨다. 정도가 되겠다. 3번 차이점은 사실 크게 중요하지는 않다. 위에 링크를 남긴 문제를 풀었다면 이 문제도 아마 크게 어렵지 않게 풀 수 있다. 문제풀이 자세한 풀이는 생략하겠다. (위 비슷한 문제와 거의 똑같은 방식으로 풀었다.) 우선, 루트 노드가 무엇인..

[C++] 백준 1967번 트리의 지름

그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다른 사람들 시간을 보니 다시 풀어야 겠다고 생각해서 다시 풀어서 제대로 맞출 수 있었다. DFS를 자유자재로 변형할 수 있으면 쉽게 맞출 수 있는 문제였다고 생각한다. 문제풀이 우선 처음 이 문제를 풀었을 때, 정점의 개수가 최대 10,000개인 것을 확인했고 간선의 개수가 최대 9,999개인 것을 확인했다. 각 정점마다 DFS를 한 번 하는데 소요되는 시간은 모든 정점을 방문했을 때, O(N)의 시간이 소요된다. 그러면 모든 정점에서 DFS를 한다면 총 소요되는 시간은 O(N^2)이다. N은 최대 10,000이..