SW 역량 테스트 A형 기출 문제1 SW 역량 테스트 A형 기출 문제 (다리 만들기 2) [다리 만들기 2 - 17472] * 로직 모든 섬을 연결하는 다리 길이의 최솟값이 이 문제의 핵심이다 각각의 섬을 노드라고 생각하고 연결된 다리를 간선으로 생각했을 때 "최소비용 신장트리"가 떠올랐다 우선, BFS를 활용해 각각 밀집해있는 덩어리들에 섬 번호를 부여해준다 이후, 섬에서 다른 섬으로 연결되는 간선의 최솟값들을 갱신하고 그래프와 간선 정보를 넣어준다 최소비용 신장트리를 위한 알고리즘을 진행한다 크루스칼 알고리즘 프림 알고리즘 (V) 만약 제대로 섬이 연결되지 않았다면 -1을 리턴한다 // A형 기출문제(다리 만들기 2) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp.. 2020. 4. 22. 이전 1 다음
