1211ghkd   1년 전

tuple 사용해서 좌표 번호랑 거리 저장했고

거리순으로 정렬한 다음

크루스칼 알고리즘 사용해서 결과값 구했습니다.

뭐가 틀렸는지 모르겠습니다.

1211ghkd   1년 전

덧붙이자면 위와 같이 그대로 제출했을때 시간 초과가 떴고 혹시 불필요한 set_find 연산 때문에 그런건가 싶어 kruskal 함수 본문을 수정해서 작성하니 틀렸다고 떴습니다.

djm03178   1년 전

몇 군데 수정이 필요합니다.

  1. 좌표의 최댓값이 100만이기 때문에,  get_distance가 반환하는 값은 int의 범위를 넘길 수 있습니다. 따라서 long long 혹은 double로 계산해야 하고, 저장하는 tuple도 long long 혹은 double을 써야 합니다.
  2. 이미 연결된 통로가 항상 아직까지 이동 경로가 없는 정점 쌍을 연결한다는 보장이 없습니다. kruskal 함수에서 한 것과 마찬가지로, set_find를 먼저 해서 두 정점이 속한 set이 다를 경우에만 union을 해야 합니다.
  3. 현재 정답을 출력하는 부분은 무조건 유효숫자가 3개가 되도록 출력하고 있습니다. 하지만 이건 예제만 제대로 나올 뿐이고, 정답의 범위가 1 이상 10 미만이 아니라면 소수점 아래 둘째자리까지 출력하지 못하게 됩니다. 다음과 같이 해야 합니다.

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