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

백준 2146번 다리만들기 JAVA 풀이

 

문제

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

2146번: 다리 만들기

 

입출력

 

문제 요약

2개 이상의 섬(1)과 바다(-1)가 표시된 N*N 배열에서 섬과 섬 사이에 하나의 다리를 놓으려 한다. 

이때 다리를 놓을 수 있는 최솟값을 구하여라.

 

예제

 

문제 접근

각 섬에서 다른 섬 까지의 최단 값을 찾는 문제이다. 해야할 것은 크게 두 가지인데, 

1. 각 섬을 구분하기 

2. 하나의 섬에서 다른 섬까지 도달하기 

 

섬을 구분하는 것은 입력으로 받은 map 에서 배열값이 '1'인 요소들을 찾고, 이 배열과 인접한 인덱스를 bfs로 하나씩 살피면서 바다인 부분은 무시하고, 섬인 부분만 체크한다. 그렇게 하면 한 덩어리의 육지를 찾아낼 수 있다. 

처음에 bfs로 찾아낸 육지에는 '2'라는 값을 부여하여 '2번 섬' 이라는 의미를 부여한다. 섬은 언제나 2번 부터 시작이다. 0과 1은 이미 배열에서 특정한 의미를 가지고 있기 때문이다. 

bfs로 섬을 찾는 행위를 배열의 끝에 다다를 때 까지 반복하다보면 2번 섬, 3번 섬, 4번 섬 .... 을 배열에 나타낼 수 있다.

 

예제 입력의 섬들에게 bfs를 이용하여 각각의 섬 번호를 부여했다.

이어진 육지끼리 분류하여 서로 다른 섬을 정의했으니, 이제 섬과 섬 사이에 다리를 놓아야 한다.

bfs를 이용하여 n번 섬에서 나머지 섬들 까지의 거리를 재며, 이를 반복한다. 만약 다음 좌표가 n번 섬이거나 이미 방문한 바다이면 무시한다. 그렇지 않다면 다른 섬과 인접한 것이 되므로 n번 섬에서 다른 섬까지 가는 데에 걸린 거리 값을 전체최소값과 비교한다.  bfs는 배열을 동서남북 방향으로 한 칸씩 방문하므로, 가장 먼저 도달한 거리가 곧 최솟값이 된다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
class Node{
    int x;
    int y;
    int cost;

    public Node(int y,int x, int cost){
        this.x=x;
        this.y=y;
        this.cost= cost;
    }
}
public class Main {
    static final int ISLAND_S_NUM = 2;
    static int N;
    static int[][] map;
    static int[] dx={0,0,1,-1};
    static int[] dy= {1,-1,0,0};
    static int min_cost=9999;
    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];

        //input start
        for(int i=0; i<N; i++){
            String[] input = br.readLine().split(" ");
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        //input end

        //search_island start
        int island_count= ISLAND_S_NUM ; // 1까지는 이미 입력에서 사용한 숫자이기 때문에 특정 섬의 고유번호는 2부터 시작
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j]==1){
                    search_island(i,j, island_count); //하나의 섬을 찾기
                    island_count++; //한 덩어리의 섬을 찾았다면, 다음 섬의 번호를 매기기 위해 island_count를 1만큼 올린다.
                }
            }
        }
        //search_island end
        //print_map();

        //create_bridge start
        for(int i=ISLAND_S_NUM; i<island_count; i++){ //섬의 고유번호인 2부터, 마지막 섬의 번호인 island_count 까지
            create_bridge(i, getCopy_map()); //다리를 만든다. 하나의 섬을 기준으로 다른 섬에 다리를 놓는 것이기 때문에
            //섬의 개수만큼 반복된다. 따라서 방문처리가 포함된 map은 깊은 복사를 하여 사용하도록 한다.
        }
        //create_bridge end

        //result
        System.out.println(min_cost);
    }

    private static void print_map() {
        Arrays.stream(map).forEach(i -> {
            Arrays.stream(i).forEach(j-> System.out.print(j+ " "));
            System.out.println();
        });
    }

    private static int[][] getCopy_map() {
        int[][] copy_map = new int[N][N];
        for(int i=0; i<N; i++){
           for(int j=0; j<N; j++){
               copy_map[i][j] = map[i][j];
           }
        }
        return copy_map;
    }

    public static void create_bridge(int island_number, int[][] map){
        Queue<Node> queue = new ArrayDeque<>();
        int cost=0;
        int ny,nx;

        for(int i=0; i<N; i++){ //island_number에 해당하는 모든 배열의 x,y를 queue에 넣는다.
            for(int j=0; j<N; j++){
                if(map[i][j]==island_number){
                    queue.add(new Node(i,j,cost));
                }
            }
        }

        while(!queue.isEmpty()){
            Node node =queue.poll();

            for(int i=0; i<4; i++){ //동,서,남,북을 방문한다.
                ny= node.y + dy[i];
                nx= node.x + dx[i];

                if(ny >= N || nx >= N || ny<0 || nx<0 || map[ny][nx]==island_number || map[ny][nx]==-1){ //범위체크
                    continue;
                }

                if(map[ny][nx]!=island_number && map[ny][nx]!=0){ //종료조건
                    min_cost=Math.min(node.cost ,min_cost);
                    break;
                }

                map[ny][nx] = -1;
                queue.add(new Node(ny,nx,node.cost+ 1));

            }
        }
    }
    public static void search_island(int y, int x ,int island_count ){
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{y,x});
        map[y][x] = island_count;

        while(!queue.isEmpty()){
            int[] yx=queue.poll();
            for(int i=0; i<4; i++){ //동,서,남,북을 방문한다.
                int ny= yx[0] + dy[i];
                int nx= yx[1] + dx[i];

                if(ny >= N || nx >= N || ny<0 || nx<0){ //범위체크
                    continue;
                }

                if(map[ny][nx]==1){
                    map[ny][nx]= island_count;
                    queue.add(new int[]{ny,nx});
                }
            }
        }
    }
}