17472. 다리 만들기 2

- 주석으로 설명을 대신한다.

- 최소 스패닝과 그래프 이론 dfs/bfs를 모두 사용하여야 하는 문제였고, 많이 배울 수 있는 문제였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B_17472_다리만들기2 {

	static int N, M;
	static int[][] arr;
	static boolean[][] visited;
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] link;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 섬에 번호 매기기
		int island = 0;
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 1 && !visited[i][j]) {
					visited[i][j] = true;
					arr[i][j] = ++island;
					dfs(i, j, island);
				}
			}
		}

		// 다리 연결하기
		link = new int[island][island];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 0)
					continue;
				makeBridge(i, j, arr[i][j]);
			}
		}

		// 모든 섬을 연결하는 최소의 다리 길이 구하기
		int result = 0; // 최종 결과값
		int[] minLength = new int[island]; // 각 섬에서의 다른 섬까지의 다리 길이
		boolean[] check = new boolean[island]; // 방문 체크
		Arrays.fill(minLength, Integer.MAX_VALUE); // 다른 섬까지의 거리를 무한대로 설정
		minLength[0] = 0; // 시작점을 정하고 시작점의 다리길이를 최소로 설정

		for (int i = 0; i < island; i++) { // 간선 수 (N-1) + 처음 시작 (1) = N(island)
			int idx = -1; // 각 섬마다의 최소 간선의 섬
			int min = Integer.MAX_VALUE; // 각 섬마다의 최소 간선(다리)의 길이

			for (int j = 0; j < island; j++) { // 현재 기준에서 최소인 다리길이 찾기
				if (check[j])
					continue;
				if (min > minLength[j]) {
					idx = j;
					min = minLength[j];
				}
			}
			if (idx == -1) { // 모든 정점과의 거리가 무한대 - 연결이 없다. (min의 무한대와 비교해서 적은 값이 없다면)
				result = -1;
				break;
			}
			check[idx] = true; // 방문체크
			result += min; // 최소 다리길이 더하기

			for (int j = 0; j < island; j++) { // 최소값 갱신
				if (!check[j] && link[idx][j] != 0 && minLength[j] > link[idx][j])
					minLength[j] = link[idx][j];
			}
		}

		System.out.println(sb.append(result));
	}

	private static void makeBridge(int y, int x, int island) {
		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];
			int cnt = 0;
			while (true) {
				if (!isArea(my, mx) || arr[my][mx] == island)
					break;
				if (arr[my][mx] == 0) { // 바다
					my += dir[i][0];
					mx += dir[i][1];
					cnt++;
				} else { // 다른 섬
					if (cnt >= 2) { // 다리 길이 2이상 - 최소의 다리길이 입력
						int next = arr[my][mx] - 1;
						link[island - 1][next] = (link[island - 1][next] == 0) ? cnt
								: Math.min(link[island - 1][next], cnt);
					}
					break;
				}
			}
		}
	}

	private static void dfs(int y, int x, int island) {
		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];
			if (!isArea(my, mx) || visited[my][mx] || arr[my][mx] != 1)
				continue;
			visited[my][mx] = true;
			arr[my][mx] = island;
			dfs(my, mx, island);
		}
	}

	private static boolean isArea(int y, int x) {
		if (y < 0 || x < 0 || y >= N || x >= M)
			return false;
		return true;
	}

	static class Edge implements Comparable<Edge> {
		int end, weight;

		public Edge(int end, int weight) {
			super();
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}

	}
}