boj 17472

[JAVA/자바 백준 17472] 다리 만들기2

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 bfs , prim 알고리즘을 사용했습니다. 1. bfs를 사용해서 섬들을 구분 지어줬습니다. 섬 2번부터 시작해서 2,3,4,5 2. 다리를 지을 수 있는 상황이면 모두 지어주고 거리에 따라 오름차순으로 정렬되게 edgeList에 넣어줬습니다. 3. prim 알고리즘을 사용하여 최소 스패닝 트리를 만들었습니다. 반례) 1. ㄷ자형 섬에 대하여 처리를 해줬습니다. 2. ..