[JAVA] 백준 2146번 【다리 만들기】

 

---

 

어제 이 문제 때문에 하루를 통으로 날렸다...

 

고민을 그만큼 많이 했던 문제, 해결을 위한 아이디어 자체는 간단하게 떠올랐는데, 이를 구현하는데 굉장히 오래 걸렸다.

 

1. 섬마다, 같은 육지는 번호를 부여해서 Labeling을 한다.

2. boolean 맵을 만들어서, 육지 부분을 True로 만들어 놓는다.

3. 섬마다 bfs를 실행해서, 다른 섬과 만나는 순간, 길이를 기록하고, 가장 최솟값을 남긴다.

 

먼저 전체 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class No_2146 {

    static int N, min = Integer.MAX_VALUE;
    static int land = 1;
    static int[][] map;
    static boolean[][] marked;
    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];
        marked = new boolean[N][N];


        //맵을 다 입력한다.
        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]);
            }
        }



        //같은 섬의 육지에 라벨링을 한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                //바다인 경우? + 이미 방문했던 육지인 경우? PASS
                if (map[i][j] == 0 || marked[i][j] == true) {
                    continue;
                }
                //방문하지 않았던 육지를 발견한 경우? dfs 실행
                dfs(i, j);

                //dfs가 끝나면, 라벨링할 land의 값을 하나 증가 시킨다.
                land++;
            }
        }

        //방문기록을 초기화한다. 남겨놀 이유가 없다. 이전 방문 기록은 dfs를 사용하기 위해 만들어둔 것일 뿐 bfs를 다시
        //작동시켜야 하기 때문에, 재활용하는 것
        marked = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                //바다인 경우? PASS
                if (map[i][j] == 0 ){
                    continue;
                }
                //처음 방문한 육지가 나오는 경우? bfs 실행
                bfs(i, j, map[i][j]);
            }
        }

        System.out.println(min);
    }


    static void dfs(int x, int y) {
        //육지이면서 (map[x][y]==1) 방문 기록이 없는 곳일 때
        if (marked[x][y] == false && map[x][y] == 1) {

            //방문 기록을 남긴다.
            marked[x][y] = true;
            //방문기록을 남기면서, land 값으로 변경한다.
            map[x][y] = land;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //이동하면서 맵 범위를 벗어나지 않거나, 방문하지 않은 육지인 경우 dfs를 재귀적으로 호출
                if (((0 <= nx && nx < N) && (0 <= ny && ny < N)) && marked[nx][ny] == false && map[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }

    static void bfs(int x, int y, int land) {
        //bfs를 사용하기 위해 만든 Queue
        Queue<int[]> q = new LinkedList<>();

        //bfs를 위해 큐에 해당 좌표를 넣는다.
        // x좌표 y좌표 다리길이(기본값은 0이다, 바다를 만나면 1씩 증가시킨다.)
        q.offer(new int[]{x, y, 0});

        //방문했던 바다인지 체크하기 위해 배열 초기화
        boolean[][] marked = new boolean[N][N];

        //큐가 완전히 빌 때까지 진행
        while (!q.isEmpty()) {
            int[] point = q.poll();
            for (int k = 0; k < 4; k++) {

                //큐에 넣었던 포인트를 기준으로 상,하,좌,우 탐색
                int nx = point[0] + dx[k];
                int ny = point[1] + dy[k];

                //맵 범위를 벗어나는 경우, PASS
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
                    continue;
                }

                //같은 섬일 경우, 다리를 놓을 수 없으므로 방문 표시만 하고 넘어간다.
                if (map[nx][ny] == land) {
                    continue;
                }

                //방문했던 바다인 경우 넘어간다.
                if (marked[nx][ny] == true) {
                    continue;
                }

                // 포인트가 0이고, 방문하지 않은 바다라면?
                if (map[nx][ny] == 0) {
                    //큐에 추가해준 뒤, 다리 길이를 1칸 늘린다.
                    // 바다 방문 표시를 남긴다.
                    q.offer(new int[]{nx, ny, point[2] + 1});
                    marked[nx][ny] = true;

                    //다른 섬에 도착했다면? 더이상 탐색을 하지 않아도 된다.
                } else if (map[nx][ny] != land) {
                    //다리 길이를 늘리지 않고, 최솟값을 확인한다.
                    min = Math.min(min, point[2]);
                    return;
                }
            }
        }
    }
}

 

1. 메인 메서드

 

먼저, 메인 메서드는 입력받는 것부터 시작한다.

 

BufferedReader를 사용해서 N을 입력받고, N*N 크기의 맵을 만든다.

 

그리고 이중 for 문을 사용해서, 입력으로 들어오는 0과 1로 이루어진 맵을 입력한다.

 

land 라는 변수를 이용해서, dfs했을때, 처음 발견되는 섬에 land = 1 값으로 쭉 라벨링하고,

 

다음 dfs 때는 land =2 로 라벨링하고... 이런식으로 번호를 부여할 것이다.

 

그 다음, bfs를 사용해서, 최단 거기를 찾을 것이다.

 

2. 섬마다 번호를 부여해서 라벨링 하기

 

 static void dfs(int x, int y) {
        //육지이면서 (map[x][y]==1) 방문 기록이 없는 곳일 때
        if (marked[x][y] == false && map[x][y] == 1) {

            //방문 기록을 남긴다.
            marked[x][y] = true;
            //방문기록을 남기면서, land 값으로 변경한다.
            map[x][y] = land;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //이동하면서 맵 범위를 벗어나지 않거나, 방문하지 않은 육지인 경우 dfs를 재귀적으로 호출
                if (((0 <= nx && nx < N) && (0 <= ny && ny < N)) && marked[nx][ny] == false && map[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }

 

먼저, 라벨링 작업은 dfs는 재귀를 이용해서 구현하였다.

 

방문 표시가 안되어있으면서, map[x][y]==1 즉, 입력받은 map에 의해서 1은 육지이기 때문에, 

 

방문 표시가 안되어 있는 붙어있는 육지 좌표는 모두 지나가게 될 것이다.

 

상,하,좌,우로 이동하면서, 맵의 범위를 벗어나지 않고, 방문하지 않았으면서, 육지라고 판단되면 land값을 부여하도록 구현하였다.

 

 

3. 최단 거리 계산하기

 static void bfs(int x, int y, int land) {
        //bfs를 사용하기 위해 만든 Queue
        Queue<int[]> q = new LinkedList<>();

        //bfs를 위해 큐에 해당 좌표를 넣는다.
        // x좌표 y좌표 다리길이(기본값은 0이다, 바다를 만나면 1씩 증가시킨다.)
        q.offer(new int[]{x, y, 0});

        //방문했던 바다인지 체크하기 위해 배열 초기화
        boolean[][] marked = new boolean[N][N];

        //큐가 완전히 빌 때까지 진행
        while (!q.isEmpty()) {
            int[] point = q.poll();
            for (int k = 0; k < 4; k++) {

                //큐에 넣었던 포인트를 기준으로 상,하,좌,우 탐색
                int nx = point[0] + dx[k];
                int ny = point[1] + dy[k];

                //맵 범위를 벗어나는 경우, PASS
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
                    continue;
                }

                //같은 섬일 경우, 다리를 놓을 수 없으므로 방문 표시만 하고 넘어간다.
                if (map[nx][ny] == land) {
                    continue;
                }

                //방문했던 바다인 경우 넘어간다.
                if (marked[nx][ny] == true) {
                    continue;
                }

                // 포인트가 0이고, 방문하지 않은 바다라면?
                if (map[nx][ny] == 0) {
                    //큐에 추가해준 뒤, 다리 길이를 1칸 늘린다.
                    // 바다 방문 표시를 남긴다.
                    q.offer(new int[]{nx, ny, point[2] + 1});
                    marked[nx][ny] = true;

                    //다른 섬에 도착했다면? 더이상 탐색을 하지 않아도 된다.
                } else if (map[nx][ny] != land) {
                    //다리 길이를 늘리지 않고, 최솟값을 확인한다.
                    min = Math.min(min, point[2]);
                    return;
                }
            }
        }
    }

 

최단거리를 계산하기 위해서는 좌표 말고도, 다리 길이를 저장할 수 있게 3개의 원소를 갖는 int[] 배열을 q에 등록시켜주어야 한다.

 

같은 섬의 육지인 경우에는, 다리길이는 증가시키지 않고, 방문 표시만하고 넘어가고, 방문하지 않은 바다를 만나는 경우에만 다리길이를 증가시켜주며 큐에 넣어주고 bfs를 계속하면 된다.

 

그러다가, 다른 라벨을 가진(land 값) 육지를 만나게 됐을 때, 다리 길이를 증가시키지 않고 이를 min값에 저장해준다.

 

각 섬마다 bfs를 하면서, 이 min 값은 계속해서 작은 값으로 갱신될 것이다!

 

 

다른 사람들은 배열을 여러개 쓴 경우도 있고, map값을 바꿔서 푼 사람도 있고 다양했지만, 가장 직관적으로 이해할 수 있는 방법으로 해결하는게 중요한 것 같다.

 

내 풀이를 보고 다른 분들도 쉽게 이 문제를 이해했으면 하는 바람이다!