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

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

풀이: bfs, 최소 스패닝 트리

1. 먼저 bfs로 섬마다 방문한 뒤 섬의 번호를 부여한 table을 생성한다.
2. 해당 table에서 직선으로 길이 2 이상의 다리를 찾아서 섬 간의 인접행렬에 업데이트한다.
3. 최종적으로 구해진 인접 행렬을 {섬1, 섬2, 거리}의 배열로 PriorityQueue에 저장한다. (거리로 정렬)
4. 유니온 파인드로 최소 스패닝 트리를 찾는다.

코드

package baekjoon.gold.g1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class p17472다리만들기2 {
	static int[] dy = new int[] {0, 0, 1, -1};
	static int[] dx = new int[] {1, -1, 0, 0};
	static int height, width;
	static boolean[][] land;
	static int[][] grid;
	static int[] parent;
	
	static int find(int a) {
		if(parent[a]==a) {
			return a;
		}
		parent[a] = find(parent[a]);
		return parent[a];
	}
	static boolean union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		if(rootA==rootB)
			return false;
		parent[rootA] = rootB;
		return true;
	}
	
	static void bfs(int posI, int posJ, int idx, boolean[][] visited) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] {posI, posJ});
		visited[posI][posJ] = true;
		grid[posI][posJ] = idx;
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			for(int i=0; i<4; i++) {
				int ni = cur[0] + dy[i];
				int nj = cur[1] + dx[i];
				if(0<=ni&&ni<height&&0<=nj&&nj<width&&!visited[ni][nj]&&land[ni][nj]) {
					visited[ni][nj] = true;
					grid[ni][nj] = idx;
					queue.offer(new int[] {ni, nj});
				}
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());
		land= new boolean[height][width];
		for(int i=0; i<height; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<width; j++) {
				if(Integer.parseInt(st.nextToken())==1) {
					land[i][j] = true;
				}
			}
		}
		int cnt = 1;
		boolean[][] visited = new boolean[height][width];
		grid = new int[height][width];
		for(int i=0; i<height; i++) {
			for(int j=0; j<width; j++) {
				if(land[i][j]&&!visited[i][j])
					bfs(i, j, cnt++, visited);
			}
		}
		cnt--;
		int INF = Integer.MAX_VALUE;
		int[][] dist = new int[cnt][cnt];
		for(int i=0; i<cnt; i++) {
			Arrays.fill(dist[i], INF);
		}
		for(int i=0; i<height; i++) {
			for(int j=0; j<width-1; j++) {
				if(grid[i][j]==0&&grid[i][j+1]!=0) {
					int d =1;
					while(j-d>=0&&grid[i][j-d]==0) {
						d++;
					}
					if(j-d>=0&&d>1) {
						dist[grid[i][j+1]-1][grid[i][j-d]-1] = Math.min(dist[grid[i][j+1]-1][grid[i][j-d]-1], d);
					}
				}
			}
		}
		for(int i=0; i<height-1; i++) {
			for(int j=0; j<width; j++) {
				if(grid[i][j]==0&&grid[i+1][j]!=0) {
					int d =1;
					while(i-d>=0&&grid[i-d][j]==0) {
						d++;
					}
					if(i-d>=0&&d>1) {
						dist[grid[i+1][j]-1][grid[i-d][j]-1] = Math.min(dist[grid[i+1][j]-1][grid[i-d][j]-1], d);
					}
				}
			}
		}
		
		PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)->o1[2]-o2[2]);
		for(int i=0; i<cnt; i++) {
			for(int j=0; j<cnt; j++) {
				if(dist[i][j]!=INF)
				queue.offer(new int[] {i, j, dist[i][j]});
			}
		}
		
		parent = new int[cnt];
		for(int i=0; i<cnt; i++) {
			parent[i] = i;
		}
		int bridge = 0;
		int bridgeCnt = 0;
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			if(union(cur[0], cur[1])) {
				bridge += cur[2];
				bridgeCnt ++;
			}
		}
		if(bridgeCnt != cnt -1) {
			System.out.println(-1);
		} else {
			System.out.println(bridge);
		}
	}
}