BOJ_17472_다리 만들기2

1

구분: 구현, 그래프 이론, 그래프 탐색, 브루트포스 알고리즘, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패님 트리

언어: Java

전략

1. 각각 섬들을 구분하기

BFS를 통해 각 섬들을 구분한다. 섬들에 숫자를 부여한다. 

 

2. 각 섬들 간의 최소 거리 구하기 

각 섬들을 하나의 정점으로 여기기 위해 각 섬들의 최소 거리를 구한다. 

각 섬들에 대해 거리를 구하는데, 한 섬에 해당하는 모든 좌표를 모두 확인한다.  그래서 최소 거리를 구한다

구한 거리는 인접 행렬에 넣어 그래프 처럼 만든다. 

 

3. MST - 최소 스패닝 트리 구하기

prim 알고리즘과 kruskal 알고리즘이 있는데 나는 prim 알고리즘을 사용했다.

 

 

---

2. 코드

package com.ssafy.webex;

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


public class Main {

	static int w, h;
	static int[][]map, matrix;
	static boolean[][] check;
	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}

	static Queue<Node> q;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		h = scanner.nextInt();
		w = scanner.nextInt();
		map = new int[h][w];
		check = new boolean[h][w];
		
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				map[i][j] = scanner.nextInt();
			}
		}
		
		q = new LinkedList<>();
		int num = 1;//각 섬에 부여할 번호
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				if(!check[i][j] && map[i][j] == 1) {
					map[i][j] = num;
					check[i][j] = true;
					q.offer(new Node(i,j));
					setnum(num++);
				}
			}
		}

		matrix = new int[num][num];//그래프 형태로 하기위한, 노드와 그 가중치를 담은 인접 향렬
		for(int i = 1; i<num; i++) {
			for(int j = 1; j<num; j++) {
				if(i==j)
					matrix[i][j] = 0;
				else
					matrix[i][j] = Integer.MAX_VALUE;
			}
		}
		
		
		//각 섬들을 노드로 봐서 이젠 그 점간의 거리를 구해보자 
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				if(map[i][j]!=0) {
					getlength(i, j);
				}
			}
		}
		
		//전체 섬의 개수는 num-1개 이다. 
		maketree(num-1);
		System.out.println(result);

	}//main
	
	//오른, 왼, 아래, 위
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	
	//지도의 섬에 번호를 붙여주는 것 
	private static void setnum(int number) {
		while(!q.isEmpty()) {
			Node node = q.poll();
			int qy = node.y;
			int qx = node.x;
			
			for(int d = 0; d<4; d++) {
				int nx = qx + dx[d];
				int ny = qy + dy[d];
				
				if(nx<0||ny<0||nx>=w||ny>=h)continue; //범위체크
				if(map[ny][nx]==0) continue;//땅이 아니라면
				if(check[ny][nx]) continue;//방문여부 확인
				
				q.offer(new Node(ny, nx));
				map[ny][nx] = number;
				check[ny][nx] = true;
				
			}
			
		}
	}//setnum
	
	//static int index;
	//각 섬 별 거리를 구하는 함수 
	private static void getlength(int y, int x) {
		
		int num = map[y][x];
		
		//4방향 탐색 쭉쭉
		for(int d = 0; d<4; d++) {
			int nx = x;
			int ny = y;
			int length = 0;//다리 길이
			int dest = 0;//목적지 
			
			while(true) {		
				nx+=dx[d];
				ny+=dy[d];
				//범위 확인
				if(nx<0||ny<0||nx>=w||ny>=h) {
					length = 0;
					break;
				}				
				//나 자신이면 이제 그만
				if(map[ny][nx]==num) {
					length = 0;
					break;
				}
				//0이면 다리를 놓을 수 있다.
				if(map[ny][nx]==0) {
					length++;
					continue;
				}
				//이건 다른 섬에 도착한 것이다. 난 이미 걸러지니까
				if(map[ny][nx]!=0) {
					dest = map[ny][nx];
					break;
				}
			}//while
			
			//다리길이가 2 미만이면 지나가 
			if(length<2)
				continue;
			
			//더 최소값으로 
			matrix[num][dest] = Math.min(length, matrix[num][dest]);
			matrix[dest][num] = matrix[num][dest];
			
		}//4방향 탐색
	}//getlength;
	
	
	//이제 최소 신장 트리를 구하는것이 필요하다.
	static int result;
	static int[] minedge;
	//num은 전체 섬 개수 
	//prim알고리즘을 이용
	private static void maketree(int num) {
		
		minedge = new int[num+1];
		Arrays.fill(minedge, Integer.MAX_VALUE);
		//시작점은 0으로 
		minedge[1] = 0;
		result = 0;
		
		boolean[] visited = new boolean[num+1];
		
		for(int i = 1; i<=num; i++) {
			
			//1. 신장트리에 포함되지 않은 정점 중 최소 간선 비용 정점 찾기
			int min = Integer.MAX_VALUE;
			int minVertex = -1; //최소간선비용의 정점 번호
			for(int j = 1; j<=num; j++) {
				if(!visited[j] && min>minedge[j]) {
					min = minedge[j];
					minVertex = j;
				}
			}
			
			if(minVertex == -1) {
				result = -1;
				return;
			}
			visited[minVertex] = true; //신장트리에 포함시킴
			result+=min;  //간선비용 누적
			
			//2. 선택된 정점 기준으로 신장트리에 연결되지 않은 타 정점과의 간선비용 최소로 업데이트 
			for(int j = 1; j<=num; j++) {
				if(!visited[j] &&  matrix[minVertex][j]!=0 && minedge[j] > matrix[minVertex][j]) {
						minedge[j] = matrix[minVertex][j];
				}
			}
			
		}
		
		
	}//mst
	
}

 

---

3

• 최소 스패닝 트리를 만드는 알고리즘이 낯설다. 공부가 많이 필요하다. 
• BFS는 Queue에 넣기 전에 방문 체크나 이런 저런 것들을 다 하고, Queue에 넣어야 한다. - 이것 때문에 모두 앞에서 조금 부끄러웠다. 이런 실수를 계속한다. 고치자 꼭!
• 섬을 구성하는 모든 점들을 통해 거리를 구해야 하는 점을 생각해내기 어려웠다.