kks227   10달 전

벽과 각 센서들을 그래프 모델링하여(노드 총 N+2개),

각 노드 사이를 통과해야 하는 거리를 간선의 cost로 두고

최소 스패닝 트리를 뽑아서 제일 마지막에 뽑히는 간선이 최대 지름이라고 생각했습니다.

어디가 잘못된 걸까요? 센서가 0개일 때도 답은 W의 절반으로 잘 나옵니다.

union-find의 경우, 각 루트 노드는 음수값을 가지며, 자신이 속한 트리의 크기를 절댓값으로 가집니다.

둘 중 더 큰 트리가 나머지를 흡수합니다. 어차피 find하며 path가 compression을 거쳐서 큰 의미는 없지만...

cubelover   10달 전

아래와 같은 데이터에서 지나갈 수 없기 때문에 0을 출력해야 하는데 0.500000을 출력합니다. 풀이에 대한 접근은 거의 다 하신 것 같네요.


1
6
4
1 0 2
3 0 2
3 5 2
5 0 2


kks227   10달 전

오오 감사합니다. 저런 경우가 있군요.

최소 스패닝 트리를 뽑기 전에, 거리가 0인 간선들의 양끝 노드만 다 union해 보고

양쪽 벽이 같은 집합에 속해 있는지를 보고 같은 집합이면 바로 0을 출력해 버리면 될까요?

cubelover   10달 전

그러면 아래와 같은 데이터에서 답이 0.5인데 1.5를 출력하게 됩니다. 0 처리를 따로 해 주는 것이 아니고 d를 구하는 방법을 조금 바꿔주시면 됩니다.


1
10
4
2 0 1
5 0 1
5 5 1
8 0 1


kks227   10달 전

오오! 덕분에 문제를 풀었습니다. 정말 감사드립니다.

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