khy2714   7달 전

BFS를 두 번 활용해서 문제를 해결했습니다.

일단 트리의 루트 노드는 트리의 아무 노드를 임의로 선택(1번 노드)해서 루트 노드라고 가정하고 풀었습니다.

먼저 모든 잎 노드를 큐에 넣은 후에 BFS를 돌려서 각 잎 노드에서 루트 노드를 향하는 방향으로 거리를 진행해주었습니다.

질문 게시판에 올라온 반례를 모두 다 적용했는데 맞는 풀이로 떠서

어느 부분이 잘못된 건지 모르겠네요ㅠ

반례나 제 코드에서 틀린 부분 알려주신다면 정말 감사드리겠습니다..!!

kokosoko59   7달 전

잎에서 루트까지의 거리중에서 최대가 트리의 지름이 아닌경우도 있습니다.

다른말로 하면, 트리의 지름은 잎에서 잎까지의 거리일수도 있습니다.

khy2714   7달 전

그래서 

if (dist[nxt] + dist[cur] + node->dist - 2 > max)
max = dist[nxt] + dist[cur] + node->dist -2 ;

이 조건문을 달아줬습니다!

khy2714   7달 전

앗 틀린 이유 찾았습니다! 감사합니다!

사용한 반례:

12
1 2 1 3 1 -1
2 1 1 4 3 5 5 -1
3 1 1 6 1 -1
4 7 2 2 3 -1
5 2 5 8 4 9 2 -1
6 3 1 10 1 11 1 -1
7 4 2 -1
8 5 4 12 5 -1
9 5 2 -1
10 6 1 -1
11 6 1 -1
12 8 5 -1

결과:

24

답:

19

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