[백준] 2146 : 다리 만들기 JAVA 풀이

 

 

1. 각각의 섬에 번호를 붙인다.

2. 각 섬에서 bfs를 수행해 다른 섬으로 가는 다리를 구해서 짧은 것으로 업데이트한다.

 

 

import java.io.*;
import java.util.*;
public class Main {

	// 지도의 크기
	static int N;
    // 섬에 붙일 번호
    // 0은 바다, 1은 섬이니 2부터
	static int landNum = 2;
    
	static int[][] map;
	static boolean[][] visit;
	
    // 가장 짧은 다리의 길이
	static int answer = Integer.MAX_VALUE;
	
    // 방향 배열
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	
	static class Node{
		int num;
		int x;
		int y;
		
		Node(int num, int x, int y){
			this.num=num;
			this.x=x;
			this.y=y;
		}
	}
	
	
	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];
		visit = new boolean[N][N];
		
		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());
			}
		}

		// 육지라면 그 육지가 몇번 섬인지 표시
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j]==1) {
					markLand(i,j);
				}
			}
		}
		
		// 번호가 붙여진 섬에 대해서 bfs를 수행해 다리를 찾음
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j]>=2) {
                	// 방문했던 걸 초기화
					visit = new boolean[N][N];
					bfs(i,j);
				}
			}
		}
		
		System.out.println(answer);
	}
	
	static void bfs(int x, int y) {
		// 큐 생성후 노드 추가
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(0, x, y));
		
        // 그 육지가 몇 번 섬인지 num에 저장
		int num = map[x][y];
		visit[x][y] = true;
	
    	// 큐가 빌 때까지 반복
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			int px = node.x;
			int py = node.y;
			
			for(int i=0;i<4;i++) {
				int nx = px+dx[i];
				int ny = py+dy[i];
				
                // 지도의 범위 안에서
				if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                	// 아직 방문하지 않았고
                    // 바다이거나 다른 섬이라면
					if(!visit[nx][ny]&&map[nx][ny]!=num) {
						visit[nx][ny] = true;
                        
                        // 바다라면 다리를 놓을 수 있으므로
                        // 다리의 길이를 1 증가 시킴
						if(map[nx][ny]==0) {
							queue.add(new Node(node.num+1,nx,ny));
						}
                        
                        // 다른 섬에 도착했다면 == 다리가 다 만들어졌다면
						else {
                        	// 기존의 가장 짧은 다리의 길이와
                            // 새로운 다리의 중 짧은 것으로
                            // answer 업데이트
							answer = Math.min(answer, node.num);
						}
					}
				}
			}
		}
		
	}
	
	
	static void markLand(int x, int y) {
    	// 큐 생성
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(0, x, y));
		
        // 방문했다고 표시 후 지도에 섬의 번호 기입
		visit[x][y] = true;
		map[x][y] = landNum;
		
        // 큐가 빌 때까지 반복 == 하나의 섬을 다 탐색할 때까지 반복
		while(!queue.isEmpty()) {
        	// 큐에서 노드 하나를 뽑아냄
			Node node = queue.poll();
			int qx = node.x;
			int qy = node.y;
			
			for(int k=0;k<4;k++) {
				int nx = qx+dx[k];
				int ny = qy+dy[k];
				
				if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                	// 아직 방문하지 않은 인접한 땅이 있다면 
					if(!visit[nx][ny]&&map[nx][ny]==1) {
                    	// 그 땅을 다시 큐에 넣고, 번호 표시 후 방문했다고 체크
						queue.add(new Node(0,nx,ny));
						visit[nx][ny] = true;
						map[nx][ny] = landNum;
					}
				}
			}
		}
        // while 문이 끝났다는 건 하나의 섬을 다 돌았다는 뜻이므로
        // 섬의 번호를 증가시킴
		landNum++;
				
	}
}