백준 17472 다리 만들기 2 (Java)

1. 문제 링크

17472번: 다리 만들기 2

 

2. 문제 및 입출력예제

 

3. 문제 풀이

bfs를 이용해 섬을 구분하여 각각 몇번째 섬인지 저장한다. 

섬 사이 거리는 dfs를 이용해 다른 섬이 나올 때까지 한다. 그 거리 중 1이 아닌 최소 거리를 저장한다.

최소 스패닝 트리를 이용하여 모든 섬을 연결하는 최소 길를 구한다.

 

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
	static int N, M, map[][], adjMatrix[][], minEdge[], idx, result;
	static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	static boolean[] islandVisit[], mstVisit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		
		map = new int[N][M];
		islandVisit = new boolean[N][M];
		
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		} //입력 끝
		
		idx = 1;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]==1 && !islandVisit[i][j]) {
					bfs(i, j, idx);
					idx++;				
				}
			}
		} //섬 구분 끝
		
		adjMatrix = new int[idx][idx];
		for(int i=0;i<idx;i++) {
			for(int j=0;j<idx;j++) {
				adjMatrix[i][j] = Integer.MAX_VALUE;
			}
		}
		
		minEdge = new int[idx];
		Arrays.fill(minEdge, Integer.MAX_VALUE);
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]!=0) { //일단 섬이 나오면 냅다 넘기자
					for(int d=0;d<4;d++) {
						dfs(i+dx[d], j+dy[d], map[i][j], 0, d);
					}
				}
			}
		}
		
		mst();
		
		for(int i=1;i<idx;i++) {
			if(!mstVisit[i]) {
				result = -1;
			}
		}
		
		System.out.println(result);
	}
	
	private static void mst() {
		int vercnt = 0;
		mstVisit = new boolean[idx];
		minEdge[1] = 0;
		
		for(int i=1;i<idx;i++) {
			int min = Integer.MAX_VALUE;
			int minVer = 0;
			
			for(int j=1;j<idx;j++) {
				if(!mstVisit[j] && min>minEdge[j]) {
					min = minEdge[j];
					minVer = j;
				}
			}
			mstVisit[minVer] = true;
			
			if(min!=Integer.MAX_VALUE)
				result += min;
			
			if(++vercnt == idx) {
				break;
			}
			
			for(int j=1;j<idx;j++) {
				if(!mstVisit[j] && adjMatrix[minVer][j]!=0 && minEdge[j] > adjMatrix[minVer][j]) {
					minEdge[j] = adjMatrix[minVer][j];
				}
			}
		}
		
	}

	private static void dfs(int i, int j, int num, int dis, int d) {
		if(i<0 || i>=N || j<0 || j>=M) { //끝까지 갔는데 섬이 안 나온 경우
			return;
		}
		
		if(map[i][j]!=0) { //끝까지 가기 전에 섬이 나왔다
			if(dis > 1) {
				adjMatrix[num][map[i][j]] = Math.min(dis, adjMatrix[num][map[i][j]]);//거리..	
			}
			return;
		}
		
		int X = i+dx[d];
		int Y = j+dy[d];
		dfs(X, Y, num, dis+1, d);
		
	}

	private static void bfs(int i, int j, int num) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] {i, j});
		islandVisit[i][j] = true;
		map[i][j] = num;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			int x = now[0];
			int y = now[1];
			
			for(int d=0;d<4;d++) {
				int X = x+dx[d];
				int Y = y+dy[d];
				if(X<0 || X>=N || Y<0 || Y>=M || map[X][Y]!=1 || islandVisit[X][Y]) {
					continue;
				}
				
				queue.offer(new int[] {X, Y});
				islandVisit[X][Y] = true;
				map[X][Y] = num;
			}
		}
	}
}