백준 17472번: 다리 만들기 2

문제 설명

• 모든 섬을 연결하는 최소비용의 다리를 구하는 문제입니다.

접근법

• 어디부터 어디까지가 하나의 섬인지를 명확히 알고있어야 합니다.(DFS)
• 모든 섬이 연결되지 않을 수 있습니다. 이를 확인하는 작업이 필요합니다(Union-Find)
• 최소비용으로 모든 섬이 연결되는 다리를 선택해야 합니다.(MST)

pseudocode

main(){
	DFS로 같은 섬에는 같은 숫자를 부여
	make_bridge함수로 0이아닌 좌표에서 상,하,좌,우로 다리를 놓아봄 (다리가 다른 섬이랑 연결되면 lst에 넣음)
    union-find를 통해 모든 다리가 연결되어 있는지 확인 
	lst에 저장한 다리를 '다리길이' 순서로 오름차순 정렬함 (최소신장트리의 개념)
    lst에서 다리를 차례로 꺼내면서 아직 연결되지 않은 두 섬에 대한 다리면 해당 다리 채택 (union)
    union이 끝난 후 최종적으로 모든 섬이 연결되었는지 확인 (parent가 모두 같은값이면 모두 연결O)
}
make_bridge(){
	for(상,하,좌,우){
    	다른 섬을 만나거나 board를 벗어날 때까지 해당 방향으로 한칸씩 전진해 봄
        만약 board를 벗어나지 않고 다른섬에 도달한 것이면서 다리의 길이가 2보다 크다면
        lst에 해당 다리를 추가(후보군으로 선택)
    }
}

정답

import java.util.*;

public class Main {
	static int N;
	static int M;
	static int score;
	static int[][] board;
	static boolean[][] v;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, -1, 0, 1 };
	static int cnt = 0; // 총 cnt개 만큼의 섬이 생성됩니다.
	static List<bridge> lst = new ArrayList<bridge>();
	static int[] parent;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int val = sc.nextInt();
				if (val == 1) {
					board[i][j] = 99; // 첫번째 섬을 1로 표현하고 싶어서 입력값 1을 다른 수(99)로 변경했습니다. (입력값 1이랑 첫번째 섬의 1이 헷갈리기 때문에)
				} else {
					board[i][j] = 0;
				}
			}
		}

		// 섬에 번호를 부여합니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 99) {
					DFS(i, j, ++cnt);
				}
			}
		}

		// 해당 섬에서 다른 섬으로 놓을 수 있는 다리가 있는지 검사합니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] != 0) {
					make_bridge(i, j);
				}
			}
		}

		// 최솟값을 도출하려면 다리의 길이가 작은 것부터 lst에서 뽑아야 하기 때문에 정렬합니다.
		Collections.sort(lst);

		// 모든 다리가 연결되어 있는지 확인하는 union-find의 parent입니다.
		parent = new int[cnt];
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
		
		// 최소신장트리(MST)를 실행합니다.
		for (int i = 0; i < lst.size(); i++) {
			bridge b = lst.get(i);
			if (union(b.from - 1, b.to - 1)) { // 새롭게 다리를 놓을 수 있다면
				score += b.length;
			}
		}

		// 최종 부모로 갱신하는 작업입니다.
		for (int i = 0; i < cnt; i++) {
			find_parent(i);
		}

		// 모든 섬이 연결되었는지 확인하는 flag입니다.
		boolean flag = false;
		for (int i = 0; i < cnt; i++) {
			if (parent[i] != parent[0]) { // 0번과 i번의 부모가 다르다는 뜻은 모든 섬이 연결되어있지 않다는 뜻입니다.
				flag = true;
			}
		}

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

	}

	public static void DFS(int x, int y, int cnt) { // 섬을 만들기 위한 DFS입니다.
		board[x][y] = cnt;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == 99) {
				DFS(nx, ny, cnt);
			}
		}
	}

	public static void make_bridge(int x, int y) {
		for (int d = 0; d < 4; d++) { // 해당 좌표에서 상,하,좌,우로 다리를 놓을 수 있는지 검사합니다.
			int nx = x + dx[d];
			int ny = y + dy[d];
			int length = 0;
			while (true) {  //d 방향으로 다리를 놓아봅니다.
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || board[nx][ny] != 0) { // 보드를 벗어나거나 다른 섬에 도달하면 while반복을 멈춥니다.
					break;
				}
				// 아직까지 board[nx][ny] == 0, 즉 물이라는 얘기입니다. 다리의 길이를 한칸 더 늘려봅니다.
				nx += dx[d];
				ny += dy[d];
				length++;
			}
			// while문을 탈출한 게 보드를 벗어나서인지 혹은 다른 섬에 도달해서인지를 확인합니다.
			if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] != 0 && length >= 2) { // 다리의 길이가 2 이상이며 다른섬에 도달해서 while을 빠져나온 거라면
				lst.add(new bridge(board[x][y], board[nx][ny], length)); // 해당 다리를 후보군에 추가합니다.
			}

		}

	}

	public static int find_parent(int x) {
		if (parent[x] == x)
			return x;
		parent[x] = find_parent(parent[x]);
		return parent[x];
	}

	public static boolean union(int a, int b) {
		int na = find_parent(a);
		int nb = find_parent(b);
		if (na > nb) {
			parent[na] = nb;
			return true;
		} else if (na < nb) {
			parent[nb] = na;
			return true;
		} else {
			return false;
		}
	}

	public static class bridge implements Comparable<bridge> {
		int from;
		int to;
		int length;

		public bridge(int from, int to, int length) {
			super();
			this.from = from;
			this.to = to;
			this.length = length;
		}

		@Override
		public String toString() {
			return "bridge [from=" + from + ", to=" + to + ", length=" + length + "]";
		}

		@Override
		public int compareTo(bridge o) {
			// TODO Auto-generated method stub
			return this.length - o.length;
		}

	}
}