1167번 - 트리의 지름
다른 정답글에서 사용된 알고리즘은
1. 임의의 노드 x에서 가장 먼 노드 a를 찾는다.
2. 노드 a에서 가장 먼 노트 b를 찾는다.
3. 트리의 지름은 노드 a에서 노드 b사이의 거리이다.
인데
저는 이렇게 생각했습니다.
1. 주어진 트리에서 가중치가 가장 큰 간선 x를 찾고 양 끝 노드를 a, b라 한다.
2. 노드 a와 연결된 방문하지 않은 sub graph중에서 가중치가 가장 큰 그래프를 선택한다.
3. 노드 b에 대해서도 2와 같은 방식으로 계산한다.
4. 간선 x의 가중치 + 노드 a에 연결된 sub graph의 가중치 + 노드 b에 연결된 sub graph의 가중치 = 트리의 지름이다.
어느 부분이 잘못되었는지 알려주시면 감사하겠습니다.
반례만이라도 알려주시면 좋겠습니다.
나름대로 구현한 코드도 첨부합니다.
반례
8
1 2 1 -1
2 1 1 3 1 -1
3 2 1 4 1 -1
4 3 1 5 1 8 2 -1
5 4 1 6 1 -1
6 5 1 7 1 -1
7 6 1 -1
8 4 2 -1
answer = 6
댓글을 작성하려면 로그인해야 합니다.
k123s456h 3년 전
다른 정답글에서 사용된 알고리즘은
1. 임의의 노드 x에서 가장 먼 노드 a를 찾는다.
2. 노드 a에서 가장 먼 노트 b를 찾는다.
3. 트리의 지름은 노드 a에서 노드 b사이의 거리이다.
인데
저는 이렇게 생각했습니다.
1. 주어진 트리에서 가중치가 가장 큰 간선 x를 찾고 양 끝 노드를 a, b라 한다.
2. 노드 a와 연결된 방문하지 않은 sub graph중에서 가중치가 가장 큰 그래프를 선택한다.
3. 노드 b에 대해서도 2와 같은 방식으로 계산한다.
4. 간선 x의 가중치 + 노드 a에 연결된 sub graph의 가중치 + 노드 b에 연결된 sub graph의 가중치 = 트리의 지름이다.
어느 부분이 잘못되었는지 알려주시면 감사하겠습니다.
반례만이라도 알려주시면 좋겠습니다.
나름대로 구현한 코드도 첨부합니다.