내일은 알고리즘

https://www.acmicpc.net/problem/17472

다리만들기 1과는 비슷한듯 전혀 다른 문제입니다.

각 섬들을 다리로 연결하는 부분은 같지만, 다리만들기1 문제와 다르게 다리는 직선으로만 가능하며 모든 섬이 연결되도록 완성해야 하고 이때 다리의 길이가 2이상인 최소한의 다리를 활용해야 합니다.

이 문제는 크게 3가지 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 최단 다리를 모두 만들기

3. 다리를 선택해 모든 섬들이 연결되게 만들기.

1,2번 과정은 다리만들기 1번 문제와 비슷하고 3번 과정은 MST(최소 스패닝 트리)를 구하는 과정으로 만들 수 있습니다.

즉, 각각의 섬들이 노드가 되고 각 섬들에서 다른섬으로 연결되는 최소거리의 다리가 엣지가 되는 식입니다.

MST를 만드는 알고리즘은 여러 종류가 있는데 우선순위 큐와 Union만을 이용해 간단하게 구현할 수 있는 크루스칼(Kruskal) 알고리즘을 사용했습니다.

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

public class q17472__BOJ_다리만들기2 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[] parent;
	static int N, M;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		int[][] map = new int[N][M];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;
		Queue<int[]> queue = new LinkedList<>();

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == -1) {
					queue.offer(new int[] { n, m });
					map[n][m] = island;

					while (!queue.isEmpty()) {
						int[] now = queue.poll();
						int x = now[0];
						int y = now[1];

						for (int i = 0; i < 4; i++) {
							int nX = x + delta[i][0];
							int nY = y + delta[i][1];
							if (isIn(nX, nY) && map[nX][nY] == -1) {
								queue.offer(new int[] { nX, nY });
								map[nX][nY] = island;
							}
						}
					}
					island++;
				}
			}
		}

		int[][] graph = new int[island][island];

		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][M];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < M; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m, 0, 5 });
						visit[n][m] = true;
					}
				}
			}

			while (!queue.isEmpty()) {
				int[] now = queue.poll();
				int x = now[0];
				int y = now[1];
				int l = now[2];
				int dir = now[3];

				if (dir == 5) {
					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 0) {
							queue.offer(new int[] { nX, nY, l + 1, i });
							visit[nX][nY] = true;
						}
					}
				}

				else {
					int nX = x + delta[dir][0];
					int nY = y + delta[dir][1];
					if (isIn(nX, nY) && !visit[nX][nY]) {

						if (map[nX][nY] == 0) {
							queue.offer(new int[] { nX, nY, l + 1, dir });
							visit[nX][nY] = true;
						} else {
							if (graph[is][map[nX][nY]] == 0 && 1 < l) {
								graph[is][map[nX][nY]] = l;
							}
							visit[nX][nY] = true;
						}
					}
				}
			}
		}

		int answer = 0;
		parent = new int[island];
		for (int n = 1; n < island; n++) {
			parent[n] = n;
		}
		PriorityQueue<int[]> pqueue = new PriorityQueue<>((e1, e2) -> {
			return e1[0] - e2[0];
		});

		for (int from = 1; from < island; from++) {
			for (int to = 1; to < island; to++) {
				if (graph[from][to] != 0) {
					pqueue.offer(new int[] { graph[from][to], from, to });
				}
			}
		}

		while (!pqueue.isEmpty()) {
			int[] now = pqueue.poll();
			int l = now[0];
			int from = now[1];
			int to = now[2];

			if (find(from) != find(to)) {
				answer += l;
				union(from, to);
			}
		}

		boolean flag = false;
		int parent = find(1);
		for (int n = 1; n < island; n++) {
			if (find(n) != parent) {
				flag = true;
				break;
			}
		}

		if (flag) {
			System.out.println(-1);
		} else {
			System.out.println(answer);
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M) {
			return true;
		}
		return false;
	}

	static int find(int i) {
		if (i == parent[i])
			return i;
		return parent[i] = find(parent[i]);
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x > y)
			parent[x] = y;
		else
			parent[y] = x;
	}
}