[백준_2146번] 다리 만들기

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

[문제]

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

 

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

 

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

 

 

 물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다). 지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

class Point_2146 {
	int x,y,count;
	
	public Point_2146(int x, int y, int count) {
		this.x=x;
		this.y=y;
		this.count=count;
	}
}
public class BaekJoon_2146 {
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	static int[][] map;
	static int n,min=Integer.MAX_VALUE,landnum=2; 
	static boolean[][] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n][n];
		visited=new boolean[n][n];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=sc.nextInt();
		
		// 섬 번호 붙이기
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				// 섬이 있는 곳이고, 아직 번호가 붙여지지 않은 곳이라면
				if(map[i][j]==1&&!visited[i][j]) {
					visited[i][j]=true; // 방문처리
					map[i][j]=landnum; // 시작 지점부터 번호 붙이기
					dfs(i,j);
					landnum++; // 한 개의 섬의 번호를 다 붙였다면 번호 증가
				}	
			}
		}
		
		// 배열의 각각의 칸에서 다른 섬까지로 가는 칸의 개수 count
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j]>=2) {
					visited=new boolean[n][n]; // 각 경우의 수 마다 방문배열 초기화
					bfs(i,j);
				}
			}
		
		}
		System.out.println(min);	
	}	
	
	// 각 섬마다 번호를 붙이는 함수(섬 번호는 2부터 시작)
	static void dfs(int x, int y) {
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			// 배열 범위 내이면서 아직 방문하지 않은 곳이고,
			if((nx<n&&ny<n&&nx>=0&&ny>=0)&&!visited[nx][ny]) {
				// 섬이 있는 곳이라면 번호 붙이기
				if(map[nx][ny]==1) {
					visited[nx][ny]=true;
					map[nx][ny]=landnum;
					dfs(nx,ny);
				}
			}
		}
	}
	
	// 다리 짓기
	static void bfs(int r, int c) {
        Queue<Point_2146> queue=new LinkedList<>();
        queue.offer(new Point_2146(r,c,0));
        int curr=map[r][c];// 현재 섬 번호
        visited[r][c]=true;
        
        while (!queue.isEmpty()) {
        	Point_2146 p=queue.poll();
        	
            for (int i=0;i<4;i++) {
                int r2=p.x+dx[i];
                int c2=p.y+dy[i];
                
                // 배열 범위 내에 있으면서 아직 방문하지 않은 곳이고
                if ((r2>=0&&r2<n&&c2>=0&&c2<n)&&!visited[r2][c2]) { 
                	// 현재 섬 번호와 다른 곳이라면
                	if(map[r2][c2]!=curr) {
                		visited[r2][c2]=true; // 방문처리
                		
                        if (map[r2][c2]==0) // 바다라면 다리 갯수를 1개 늘리고 새로운 좌표 큐에 삽입
                            queue.offer(new Point_2146(r2,c2,p.count+1));
                        else // 다른 섬을 만났다면 다리 갯수의 최솟값 갱신
                            min=Math.min(min,p.count);           
                	}
                }
            }
        }
    }
}

 

[고찰] 

이번 문제는 DFS와 BFS를 모두 사용하여 해결할 수 있었다. 우선 각 섬을 구분해야 하기 때문에 DFS 알고리즘을 사용하여 각 섬마다 번호를 붙여주었다. 해당 작업이 끝났다면 BFS 함수를 사용하여 배열의 각 칸마다 다른 칸으로 가는 칸의 개수를 count 해주었다. 현재 칸으로부터 상, 하, 좌, 우를 탐색하는데 바다라면 다리의 개수를 1 증가하고 해당 칸에서 재탐색을 해주고, 다른 섬이라면 여태까지 지은 다리의 개수와 최솟값을 비교하여 갱신해주었다. 

 이번 문제는 평소 풀던 BFS와 DFS를 섞어놓은 듯한 문제라 어렵지 않게 풀 수 있었다.