kjh107704   9달 전

크루스칼 알고리즘을 이용하였습니다.

질문을 검색해 보다가 총 세가지의 수정을 하였습니다.

1. 통로의 길이가 int범위를 넘을 수 있다고 하여 long double 형으로 수정하였습니다.

2. 처음에는 출력 형식에서 소수점 둘째 자리 까지만 잘라서 출력했는데, 반올림 문제일까 싶어 반올림 하여 출력하는 것으로 수정하였습니다.

3. 행성의 번호를 0번부터 붙이기에 disjointSet에서도 0 ~ V-1까지의 그룹을 생성하였고, 이미 연결된 행성들의 번호를 받을 때에는 행성의 번호를 0번부터 붙인 점을 감안하여 u-1, v-1 의 그룹을 확인하도록 하였습니다.

어디가 잘못된 것인지 도저히 찾을 수가 없어서 질문 올립니다. 반례나 코드에서 수정해야할 점을 알려주시면 감사하겠습니다.

Green55   9달 전

입력에서 인접한 정점끼리만 연결하여 n-1개의 간선만 만드시는거 같은데,

모든 정점쌍에 대하여 간선을 만들어줘야 합니다.

kjh107704   9달 전

아.. 놓치고 있었네요. 해당 부분 바꾸고 해결했습니다. 감사합니다.

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