백준_17472_다리만들기

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

 

문제를 요약하면 N,M 크기의 격자판위에 1로 모인곳이 섬이고 모든 섬들을 연결하는 다리길이의

최솟값을 구하는 문제이다

 

조건 ! 

1.  1번과 2 번이 연결되있고 2번과 3번이 연결되어있으면 1번과 3번도 연결되어있는것이다

2.  다리의 길이는 2이상이다.

3.  다리는 섬과 인접하게만 이어질수있다 (백준 문제예시에 그림으로 친절하게  알려준다)

 

풀이 !

 

1. 크루스칼 알고리즘을 사용하면 쉽게 풀수있다. 크루스칼 알고리즘은 최소신장트리 에관한내용인데

   아래 동빈나님 블로그에 가면 동영상강의와 함께 친절하게 내용설명을 해주신다. 

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https:%2F%2Fwww.google.com%2F

18. 크루스칼 알고리즘(Kruskal Algorithm)

2. 일단 모든 섬들이 1로만 표시되기 때문에 섬들을 구분하기 위해서 각 섬들에 번호를 매겨준다.

    번호를 매김과 동시에 섬이 몇개인지도 알수있다.

	for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(!check[i][j] && map[i][j] == 1) {
					check[i][j] = true;
					map[i][j] = ++index;
					numbering(i, j);
					
				}
			}
		}	
    
    public static void numbering(int x, int y) {

		for(int i = 1; i <= 4; i++) {
			int new_x = x + xx[i];
			int new_y = y + yy[i];
			if(new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= m) {
				if(map[new_x][new_y] != 0 && !check[new_x][new_y]) {
					check[new_x][new_y] = true;
					map[new_x][new_y] = index;
					numbering(new_x, new_y);
				}
			}
		}
		
	}

 

 

 

3. DFS 를 이용하여 A 섬에서 B 섬으로 길이 Length 의 다리를 이을수 있는경우 우선순위 큐에 담아준다.

   이때 우선순위 큐는 Length 의 길이가 짧은 순으로 담아준다. 모든 간선정보를 길이가 짧은 순으로 나열해놓고

   사이클이 생기지 않도록하는 크루스칼 알고리즘을 적용하기 위해서이다.

 

4. 마지막으로 우선순위 큐에 담긴 정보를 가지고 크루스칼 알고리즘을 돌려주면 다리의 최솟값을 알수 있다

   여기서 중요한점은 최소신장트리의 간선개수(다리)는 노드(섬)의 개수 - 1  이여야한다. 다음은 전체 코드이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;



public class Bj_17472 {
	static int[][] map;
	static boolean[][] check;
	static int n, m;
	static int parent[];
	static int index = 0;
	static int[] xx = {0, -1, 0, 1, 0};
	static int[] yy = {0, 0, 1, 0, -1};
	static int min = 0;
	static PriorityQueue<Slur> pq = new PriorityQueue<Slur>();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n + 1][m + 1];
	    check = new boolean[n + 1][m + 1];
	    
	    
	    for(int i = 1; i <= n; i++){
	    	for(int j = 1; j <= m; j++){
	    		map[i][j] = sc.nextInt();
	    	}
	    }
	    
	    //섬을 넘버링하는 부분 index에 섬 개수 정보가 저장
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(!check[i][j] && map[i][j] == 1) {
					check[i][j] = true;
					map[i][j] = ++index;
					numbering(i, j);
					
				}
			}
		}
		//크루스칼 알고리즘에서 쓰일 parent 배열 
		parent = new int[index + 1];
		for(int i = 1; i <= index; i++) {
			parent[i] = i;
		}
        // 모든 다리정보(섬 a, 섬 b , 다리길이 length)를 구하여 그정보를 우선순위큐에 담아준다.
		findEdge();		
        
        // 담긴 다리정보를 통하여 크루스칼 알고리즘을 돌려준다. 
		System.out.println(kruscal());

	}
	
	public static void numbering(int x, int y) {

		for(int i = 1; i <= 4; i++) {
			int new_x = x + xx[i];
			int new_y = y + yy[i];
			if(new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= m) {
				if(map[new_x][new_y] != 0 && !check[new_x][new_y]) {
					check[new_x][new_y] = true;
					map[new_x][new_y] = index;
					numbering(new_x, new_y);
				}
			}
		}
		
	}
	
	
	
	public static void findSum(int x, int y, int dir, int length, int sumNum) {
		int new_x = x + xx[dir];
		int new_y = y + yy[dir];
		
		if(new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= m) {
			if(sumNum != map[new_x][new_y]) {
				if(map[new_x][new_y] != 0) {
					pq.add(new Slur(sumNum, map[new_x][new_y], length));
				}else {
					findSum(new_x, new_y, dir, length + 1, sumNum);
				}	
			}
		}
	}
	
	public static void findEdge() {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(map[i][j] != 0) {
					for(int k = 1; k <= 4; k++) {
						findSum(i, j, k, 0, map[i][j]);
					}
				}
			}
		}
	}
	
	public static int kruscal() {
		
		int cnt = 0;
		
		while(!pq.isEmpty() && cnt < index) {
			Slur temp = pq.poll();
			if(temp.length == 1) {
				continue;
			}
			if(!find(temp.a, temp.b)) {
				unionParent(temp.a, temp.b);
				cnt++;
				min += temp.length;
			}
		
		}
        // 최소신장 트리에서 간선의 개수는 노드의 개수 - 1 개여야함
		if(cnt == index - 1) return min;
		else return -1;
	}
	
    // 아래는 크루스칼 알고리즘에 쓰이는 부분들 알고있으면 매우 유용하다.
	public static int  getParent(int x) {
		if(parent[x] == x) return x;
		return parent[x] = getParent(parent[x]);
	}
	public static void unionParent(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}
	public static boolean find(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		return a == b ? true : false;
	}
	
}

class Slur implements Comparable<Slur>{
	int a,b,length;
	Slur(int a, int b, int length){
		this.a = a;
		this.b = b;
		this.length = length;
	}
	public int compareTo(Slur o) {
		return this.length - o.length;
	}
	
}