1774번 - 우주신과의 교감
크루스칼 알고리즘을 이용하였습니다.
질문을 검색해 보다가 총 세가지의 수정을 하였습니다.
1. 통로의 길이가 int범위를 넘을 수 있다고 하여 long double 형으로 수정하였습니다.
2. 처음에는 출력 형식에서 소수점 둘째 자리 까지만 잘라서 출력했는데, 반올림 문제일까 싶어 반올림 하여 출력하는 것으로 수정하였습니다.
3. 행성의 번호를 0번부터 붙이기에 disjointSet에서도 0 ~ V-1까지의 그룹을 생성하였고, 이미 연결된 행성들의 번호를 받을 때에는 행성의 번호를 0번부터 붙인 점을 감안하여 u-1, v-1 의 그룹을 확인하도록 하였습니다.
어디가 잘못된 것인지 도저히 찾을 수가 없어서 질문 올립니다. 반례나 코드에서 수정해야할 점을 알려주시면 감사하겠습니다.
입력에서 인접한 정점끼리만 연결하여 n-1개의 간선만 만드시는거 같은데,
모든 정점쌍에 대하여 간선을 만들어줘야 합니다.
아.. 놓치고 있었네요. 해당 부분 바꾸고 해결했습니다. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
kjh107704 3년 전
크루스칼 알고리즘을 이용하였습니다.
질문을 검색해 보다가 총 세가지의 수정을 하였습니다.
1. 통로의 길이가 int범위를 넘을 수 있다고 하여 long double 형으로 수정하였습니다.
2. 처음에는 출력 형식에서 소수점 둘째 자리 까지만 잘라서 출력했는데, 반올림 문제일까 싶어 반올림 하여 출력하는 것으로 수정하였습니다.
3. 행성의 번호를 0번부터 붙이기에 disjointSet에서도 0 ~ V-1까지의 그룹을 생성하였고, 이미 연결된 행성들의 번호를 받을 때에는 행성의 번호를 0번부터 붙인 점을 감안하여 u-1, v-1 의 그룹을 확인하도록 하였습니다.
어디가 잘못된 것인지 도저히 찾을 수가 없어서 질문 올립니다. 반례나 코드에서 수정해야할 점을 알려주시면 감사하겠습니다.