cfghj101   2년 전

입력 부분만 달리하고 1967번과 같은 방식을 썼지만 왜 4%즈음 시간초과가 나는 것일까요?


1번 노드와 가장 멀리 떨어진 노드 x를 찾고,

x에서 가장 멀리 떨어진 노드를 찾기 위해 DFS를 총 2번 사용하여 풀었습니다.

djm03178   2년 전

n1에 대해 n2로 연결된 간선이 한 번 입력으로 주어지고, n2에 대해 n1으로 연결된 간선 역시 입력으로 주어집니다. 그런데 32, 33번째 줄에서는 각각에 대해 양쪽에 모두 push_back을 하고 있기 때문에, n1에서는 n2에 연결된 정보를 2개, n2에서도 n1에 연결된 정보를 2개씩 가지고 있습니다. 이 때문에 dfs를 할 때 같은 정점에 대해 호출을 2번씩 하는 결과를 낳습니다.

댓글을 작성하려면 로그인해야 합니다.