whwoals21   3년 전

BFS 를 활용하여 풀이에 성공하였으나

DFS를 이용해 처음 구현했던걸로 풀어보고 싶은데 모든 반례가 나오지만 49%에서 WA를 받습니다.

로직은:

Tree를 구성하면서 Out Degree를 갱신, OutDegree가 0인 즉 Leaf 노드를 Queue 에 담아둔다

Queue에 담은 Leaf 노드들을 하나 씩 DFS를 돌며 다른 Leaf를 만났을때 정답값을 max로 비교하며 최신화해준다.

Leaf 마다 DFS, 매번 memset으로 초기화 등 시간을 매우 많이쓰기때문에 시간초과가 나올거라 예상했는데 WA를 받습니다.

exponential_e   3년 전

반례 드립니다.

6 -> 2 -> 3 -> 4 -> 5 를 연결하는 길이가 지름이 될텐데, 10이라는 값이 나오네요.

whwoals21   3년 전

감사합니다

rooni97   2년 전

반례 감사합니다

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