[BOJ] 백준 2146번 다리 만들기 (Java)

#2146 다리 만들기

난이도 : 골드 3

유형 : 그래프 탐색/ BFS

2146번: 다리 만들기

▸ 문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

 

▸ 입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

 

▸ 출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

 

 

 

문제 풀이 

해당 문제는 BFS 그래프 탐색 문제이다. 섬의 크기를 구하는 문제였다면 무지 쉬웠겠지만 살짝 변형으로 섬과 섬 사이의 최단거리를 구하는 문제이다.

 

일단 모든 육지는 1로 주어지기 때문에 섬끼리의 구분이 되질 않는다. 그래서 섬 구분을 해주는 것이 첫 번째이고 그 다음으로 섬 구분이 되면은 그 때 최단거리를 구해주면 될 것 같다.

 

📚 조건

  ∙  지도 크기 N (1 <= N <= 100)

  ∙  0은 바다, 1은 육지

  ∙  항상 섬은 두개 이상

 

조건을 보니 지도 최대 크기가 그렇게 크지않아서 효율성 테스트는 그렇게 신경쓰지 않아도 될 것 같다.

 

 

섬 구분하기

첫 번째로, 섬을 구분해주자.

 

이는 간단하게 BFS 탐색으로 브루트포스하게 그래프 전체를 조회해주면 된다. (이중포문 n^2)

조건은 그래프의 값이 1인 곳을 탐색하면서 각 섬마다 특정 idx값을 부여해주고 이미 방문한 육지는 재방문이 안되게 방문여부를 잘 체크해주면 된다.

 

해당 로직 코드는 다음과 같다.

static void IslandCount() {
	int idx = 2; 
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			if(!check[i][j] && map[i][j] != 0) {
				map[i][j] = idx;
				check[i][j] =true;
				q.add(new Node(j,i,0));
				
				while(!q.isEmpty()) {
					Node pos = q.poll();
					int px = pos.x;
					int py = pos.y;
					
					for(int d=0; d<4; d++) {
						int nx = px + dx[d];
						int ny = py + dy[d];
						
						if(nx<0 || nx>n-1 || ny <0 || ny>n-1) continue;
						if(check[ny][nx]) continue;
						
						if(map[ny][nx] == 1) {
							check[ny][nx] = true;
							map[ny][nx] = idx;
							q.add(new Node(nx,ny,0));
						}
					}
				}
				idx++;
			}
		}
	}
}

 

 

섬과 섬사이 최단거리 구하기

두 번째로, 섬과 섬사이의 최단거리를 구해야 한다.

 

이는 BFS탐색을 하면서 움직인 횟수만 count해주면 된다. 한 가지 추가해야하는 옵션은 같은 섬은 방문하면 안된다. 예를 들어, 2번 인덱스 섬을 방문할 때 다른 2번 육지를 방문하면 안되고 0인 바다와 다른 육지만 방문할 수 있다. 그리고 다른 육지를 방문하면 탐색을 종료시킨다.

 

해당 로직 코드는 다음과 같다.

public static void main(String[] args) throws IOException{
	int min = Integer.MAX_VALUE;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			if(map[i][j] > 0) {
				check = new boolean[n][n];
				int res = bridge(j,i);
					
				if(res == -1 )continue;
				if(min > res) {
					min = res;

				}					
			}
		}
	}
	System.out.println(min-1);
}
	


static int bridge(int x, int y) {
	q = new LinkedList<>();
	
	int num = map[y][x];
	check[y][x] =true;
	q.add(new Node(x,y,0));
	
	while(!q.isEmpty()) {
		Node pos = q.poll();
		int px = pos.x;
		int py = pos.y;
		int bridge = pos.bridge;
		
		if(map[py][px] != 0 && map[py][px] != num) {
			return bridge;
		}
		
		for(int i=0; i<4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
			
			if(nx<0 || nx>n-1 || ny <0 || ny>n-1) continue;
			if(check[ny][nx] ||map[ny][nx] == num) continue;
			
			check[ny][nx] = true;
			q.add(new Node(nx,ny, bridge+1));
		}
	}
	return -1;
}

 

 

풀이 코드  

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static int[][] map;
	static boolean[][] check;
	static Queue<int[]> q;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		map = new int[n][n];
		check = new boolean[n][n];
		q = new LinkedList<>();
		
		
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		IslandCount();
		
		
		int min = Integer.MAX_VALUE;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(map[i][j] > 0) {
					check = new boolean[n][n];
					int res = bridge(j,i);
					
					if(res == -1 )continue;
					if(min > res) {
						min = res;
//						System.out.println("다리 완성 " + res );
					}
				}
			}
		}
		System.out.println(min-1);
	}
	
	static int bridge(int x, int y) {
		q = new LinkedList<>();
		
		int num = map[y][x];
		check[y][x] =true;
		q.add(new int[]{x,y,0});
		
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			int px = pos[0];
			int py = pos[1];
			int bridge = pos[2];
			
			if(map[py][px] != 0 && map[py][px] != num) {
				return bridge;
			}
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx<0 || nx>n-1 || ny <0 || ny>n-1) continue;
				if(check[ny][nx] ||map[ny][nx] == num) continue;
				
				check[ny][nx] = true;
				q.add(new int[] {nx,ny, bridge+1});
			}
			
		}
		return -1;
		
	}
	
	static void IslandCount() {

		int idx = 2; 
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(!check[i][j] && map[i][j] != 0) {
					map[i][j] = idx;
					check[i][j] =true;
					q.add(new int[] {j,i});
					
					while(!q.isEmpty()) {
						int[] pos = q.poll();
						int px = pos[0];
						int py = pos[1];
						
						for(int d=0; d<4; d++) {
							int nx = px + dx[d];
							int ny = py + dy[d];
							
							if(nx<0 || nx>n-1 || ny <0 || ny>n-1) continue;
							if(check[ny][nx]) continue;
							
							if(map[ny][nx] == 1) {
								check[ny][nx] = true;
								map[ny][nx] = idx;
								q.add(new int[] {nx,ny});
							}
						}
					}
					idx++;
				}
			}
			
		}
		
	}
}

 

+ 해당 BFS 로직에서 주의 할 점은 필요없는 계산은 조건으로 최대한 줄여야 한다는 것이다. 처음에 bridge값을 받을 때 return을 해주지 않아 뒤에 쓸데 없는 연산들로 인해 실행시간이 굉장히 느렸었다. 

if(map[py][px] != 0 && map[py][px] != num) {
	if(bridgeLen > pBridge) {
		bridgeLen = pBridge;
	}
    // return!
}

 

 

어차피 BFS탐색은 인접 노드부터 탐색하기 떄문에 제일 먼저 찾은 값이 가장 최단 거리이기 때문에 값을 받으면 무조건 return을 시켜 뒤에 쓸데없는 연산은 종료시키자!