BOJ 다리만들기2
-
[BOJ] #17472 _ 다리 만들기 2Problem Solving/BOJ 2019. 10. 22. 22:58
[다리 만들기 2] https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net map의 정보를 0과 1로만 준다. 따라서, 바다를 각 숫자로 만들어주고, 최단 거리를 구한 후, 모두 연결되어 있는지 확인하였다. getNewMap() 함수를 통해 아래와 같이 바다를 각 숫자로 변경해주었다. getDistMap() 함수를 통해 각 바다의 거리를 구해주었다. 최단거리를 구하고, 모두 연결되어 있는지 확인하기 위해 크루스칼 알고리즘을 사용하..