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

🔗 2146번 : 다리 만들기
● Java 풀이
● 시간 제한 2초
● 메모리 제한 192 MB

문제

 

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

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

 

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

 

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

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

 

테스트 케이스

// input
6
0 0 0 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 1

// answer
4

/** 출처 (https://www.acmicpc.net/board/view/98393) **/
// input
10
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1

// answer
17

/** 출처 (https://www.acmicpc.net/board/view/131678) **/
// input
2
1 0
0 1

// answer
1

/** 출처 (https://www.acmicpc.net/board/view/123397) **/
// input
6
1 1 0 0 0 1
1 1 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 1 1

// answer
2

// input
6
1 0 0 1 1 1
1 0 0 0 0 1
1 0 0 0 0 0
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0

// answer
1

 

풀이

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

public class Main {
    private static class Pos {
        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }

        int r, c;
    }

    private static class Sea {
        public Sea(int land, int move) {
            this.land = land;
            this.move = move;
        }

        int land, move;
    }

    private static int N, MIN_BRIDGE; // 지도의 크기
    private static int[][] map; // 지도
    private static Sea[][] dp;
    private static Queue<Pos> queue;
    private static final int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        /* 초기 설정 */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        queue = new ArrayDeque<>();

        N = Integer.parseInt(br.readLine());  // 지도 크기 입력 받기
        map = new int[N][N];  // 지도 크기 초기화
        dp = new Sea[N][N];
        MIN_BRIDGE = 100 * 100;

        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());
            }
        }

        findLand();  // 섬 구분하기
        findClosedSea();  // 설치 가능 다리 구분하기
        System.out.println(MIN_BRIDGE);
    }

    private static void findLand() {
        int checkNum = 2;  // 2부터 구분 (1은 섬 자체를 체크하는 정수이기 때문)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {  // 구분되지 않은 섬일 경우
                    map[i][j] = checkNum;  // 해당 섬의 구분 index는 checkNum
                    checkLand(i, j, checkNum++);  // BFS로 해당 섬을 구분하는 함수 호출
                }
            }
        }
    }

    private static void checkLand(int r, int c, int checkNum) {
        Pos pos;
        int mr, mc;
        queue.add(new Pos(r, c));
        while (!queue.isEmpty()) {  // BFS 순환
            pos = queue.poll();
            for (int i = 0; i < 4; i++) {  // 사방 탐색
                mr = pos.r + dr[i];
                mc = pos.c + dc[i];
                if (0 <= mr && mr < N && 0 <= mc && mc < N && map[mr][mc] == 1) {  // 연결되는 + 구분되지 않은 섬일 경우
                    map[mr][mc] = checkNum;  // checkNum index로 구분
                    queue.add(new Pos(mr, mc));  // 해당 위치의 주변 탐색하기 위해 queue에 삽입
                }
            }
        }
    }

    private static void findClosedSea() {
        int mr, mc;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {  // 완전 탐색
                if (map[i][j] == 0) {  // 해당 위치가 바다일 경우
                    for (int k = 0; k < 4; k++) {  // 사방 탐색
                        mr = i + dr[k];
                        mc = j + dc[k];
                        if (0 <= mr && mr < N && 0 <= mc && mc < N && 1 < map[mr][mc]) {  // 섬과 인접해있는 바다일 경우
                            dp[i][j] = new Sea(map[mr][mc], 1);  // 설치 가능 다리 길이 (1) 초기화
                            checkSea(i, j, map[mr][mc]);  // BFS로 해당 위치에서부터 설치 가능 다리 길이 탐색할 함수 호출
                        }
                    }
                }
            }
        }
    }

    private static void checkSea(int r, int c, int land) {
        queue.add(new Pos(r, c));
        Pos pos;
        int mr, mc;
        while (!queue.isEmpty()) {  // BFS 순환
            pos = queue.poll();

            for (int i = 0; i < 4; i++) {  // 사방 탐색
                mr = pos.r + dr[i];
                mc = pos.c + dc[i];

                if (0 <= mr && mr < N && 0 <= mc && mc < N && dp[pos.r][pos.c].move < MIN_BRIDGE) {  // 현재 다리 길이가 최소 다리 길이보다 짧을 경우 + 이동 가능할 경우
                    if (0 < map[mr][mc]) {  // 섬에 도달했을 경우
                        if (map[mr][mc] != land) {  // 도달한 섬이 출발 섬과 다른 섬일 경우
                            MIN_BRIDGE = Math.min(MIN_BRIDGE, dp[pos.r][pos.c].move);  // 최단 거리 초기화
                        }
                    } else if (dp[mr][mc] != null && dp[mr][mc].land != land) { // 이미 잰 거리가 존재 + 다른 섬에서 잰 거리일 경우
                        MIN_BRIDGE = Math.min(MIN_BRIDGE, dp[pos.r][pos.c].move + dp[mr][mc].move);  // 최단 거리 초기화
                    } else if (dp[mr][mc] == null && dp[pos.r][pos.c].move + 1 < MIN_BRIDGE) {  // 잰 거리가 없음 + 최소 다리 길이보다 짧을 경우
                        dp[mr][mc] = new Sea(land, dp[pos.r][pos.c].move + 1);  // 설치 가능 다리 길이 초기화
                        queue.add(new Pos(mr, mc));  // 해당 위치의 주변 탐색하기 위해 큐에 삽입 
                    } else if (dp[mr][mc] != null && dp[pos.r][pos.c].move + 1 < dp[mr][mc].move) {  // 이미 잰 거리가 존재 + 출발 섬에서 잰 거리지만, 더 짧게 다리를 세울 수 있을 경우
                        dp[mr][mc] = new Sea(land, dp[pos.r][pos.c].move + 1);  // 더 짧은 거리의 다리로 초기화
                        queue.add(new Pos(mr, mc));  // 해당 위치의 주변 탐색하기 위해 큐에 삽입
                    }
                }
            }
        }
    }
}

/*
public class BJ02146_다리만들기 {
    private static class Pos {
        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }

        int r, c;
    }
    private static int N, MIN_BRIDGE; // 지도의 크기
    private static int[][] map; // 지도
    private static int[][][] dp;
    private static Queue<Pos> queue;
    private static final int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        queue = new ArrayDeque<>();
        MIN_BRIDGE = 100 * 100;

        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());
            }
        }

        findLand();  // 육지 구분하기
        //printMap();
        selectBridge();  // 섬을 연결하는 짧은 다리 찾기
        //printDp(3);
        System.out.println(MIN_BRIDGE);
    }

    private static void findLand() {
        int checkNum = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == -1) {
                    map[i][j] = checkNum;
                    checkLand(i, j, checkNum++);
                }
            }
        }
        dp = new int[checkNum][N][N];
    }

    private static void checkLand(int r, int c, int checkNum) {
        Pos pos; int mr, mc;
        queue.add(new Pos(r, c));
        while (!queue.isEmpty()) {
            pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                mr = pos.r + dr[i];
                mc = pos.c + dc[i];
                if(0 <= mr && mr < N && 0 <= mc && mc < N && map[mr][mc] == -1) {
                    map[mr][mc] = checkNum;
                    queue.add(new Pos(mr, mc));
                }
            }
        }
    }

    private static void selectBridge() {
        int mr, mc;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 0) {  // 바다일 경우
                    for (int k = 0; k < 4; k++) {
                        mr = i + dr[k];
                        mc = j + dc[k];
                        if(0 <= mr && mr < N && 0 <= mc && mc < N && 0 < map[mr][mc] && (dp[map[mr][mc]][i][j] == 0 || 1 < dp[map[mr][mc]][i][j])) {  // 육지와 인접해있을 경우
                            //System.out.println("좌표 (" + i + ", " + j + ") 바다는 육지와 인접해있습니다");
                            dp[map[mr][mc]][i][j] = 1;
                            checkBridge(i, j, map[mr][mc]);
                            break;
                        }
                    }
                }
            }
        }
    }
    private static void checkBridge(int r, int c, int checkNum) {
        Pos pos; int mr, mc;
        queue.add(new Pos(r, c));
        while (!queue.isEmpty()) {
            pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                mr = pos.r + dr[i];
                mc = pos.c + dc[i];
                if(0 <= mr && mr < N && 0 <= mc && mc < N) {  // 이동 가능할 때,
                    if(map[mr][mc] == 0 && (dp[checkNum][mr][mc] == 0 || dp[checkNum][pos.r][pos.c] + 1 < dp[checkNum][mr][mc])) {
                        dp[checkNum][mr][mc] = dp[checkNum][pos.r][pos.c] + 1;
                        queue.add(new Pos(mr, mc));
                    } else if(0 < map[mr][mc] && map[mr][mc] != checkNum) {
                        MIN_BRIDGE = Math.min(MIN_BRIDGE, dp[checkNum][pos.r][pos.c]);
                    }
                }
            }
        }
    }

    private static void printMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.printf("%-2d", map[i][j]);
            }
            System.out.println();
        }
    }
    private static void printDp(int num) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.printf("%-2d", dp[num][i][j]);
            }
            System.out.println();
        }
    }
}
*/

 

오늘의 코드 길이가 엄청나게 긴 이유는... 어쨌든 BFS로 풀어도 정답은 정답이기 때문이다.

민망하지만 내 코드 제출을 가져와보자면, 제일 아래가 BFS로 푼 문제의 정답이다. (주석 코드)

맞긴 맞지만 찝찝한 마음에 제출 현황을 보았는데, Java로 훨씬 효율 좋은 코드를 짠 사람들이 있길래 참고해서 다시 풀어냈다.

 

다리 길이를 반복해서 계산하지 않더라도, n번 섬에서 출발한 다리가 (n - m)번 섬에서 출발한 다리 길이와 만났을 때의 계산을 해준다고 생각하면 될 것 같다.

왜 중간에서 만날 수 있다고 생각하냐면,  계산된 최단 길이를 넘었을 때 더이상 그 다리를 잇지 않기 때문에 중간에서 끊길 수가 있기 때문이다.

 

최대 값은 나는 생각없이 100 * 100으로 두었는데, 행렬의 크기가 각 100일 때 100 X 100에서의 map[0][0]부터 map[99][99]까지의 거리가 최단거리일 테니까 200으로 두어도 된다.