[BOJ] 2146 - 다리 만들기 JAVA

www.acmicpc.net/problem/2146

2146번: 다리 만들기

문제

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

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

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

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

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

입력

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

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

예제 입력 1

10

1 1 1 0 0 0 0 1 1 1

1 1 1 1 0 0 0 0 1 1

1 0 1 1 0 0 0 0 1 1

0 0 1 1 1 0 0 0 0 1

0 0 0 1 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 0 0 0 0

0 0 0 0 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0

예제 출력 1

3

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r;
    int c;
    public Pair(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    static int[][] map = null;
    static int[][] component = null;
    static boolean[][] check = null;

    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    static int n;

    public static void dfs(int r, int c, int comp) {
        for(int i = 0; i < 4; i++) {
            int nr = r + rArr[i];
            int nc = c + cArr[i];
            if(0 <= nr && nr < n && 0 <= nc && nc < n &&
                    map[nr][nc] == 1 && !check[nr][nc]) {
                check[nr][nc] = true;
                component[nr][nc] = comp;
                dfs(nr, nc, comp);
            }
        }
    }

    public static int bfs() {
        int ans = n * n;  // 다리의 길이는 n^2을 넘을 수 없다
        Queue<Pair> que = new ArrayDeque<>();
        for(int i = 0; i < n; i++) {  // 일단 모든 섬들을 큐에 담는다. 한 섬당 한 칸 씩 차례대로 다리를 올릴 것이다
            for(int j = 0; j < n; j++) {
                if(map[i][j] == 1) {
                    que.add(new Pair(i, j));
                }
            }
        }

        while(!que.isEmpty()) {
            Pair p = que.poll();
            for(int i = 0; i < 4; i++) {
                int nr = p.r + rArr[i];
                int nc = p.c + cArr[i];
                if(0 <= nr && nr < n && 0 <= nc && nc < n) {
                    if(map[nr][nc] == 0) {
                        map[nr][nc] = map[p.r][p.c] + 1;  // 다리를 한 칸 올린다
                        component[nr][nc] = component[p.r][p.c];  // 새로 올라간 다리도 섬의 일부로 친다
                        que.add(new Pair(nr, nc));
                    }else {
                        if(component[nr][nc] == component[p.r][p.c]) {  // 같은 섬은 패스
                            continue;
                        }else {  // 다른 섬 만남
                            // 다른 섬을 만났을 때 (우리 섬에서 올린 다리길이 + 다른 섬에서 올린 다리길이)가 합쳐진 다리의 길이이다
                            // 두 섬을 잇는 다리가 완성되었으니 더이상 큐에 추가하지 않는다
                            int bridge = (map[p.r][p.c] - 1) + (map[nr][nc] - 1); // 섬의 숫자 1까지 길이에 포함되었으니 -1
                            ans = Math.min(ans, bridge);
                        }
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        component = new int[n][n];
        check = new boolean[n][n];
        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());
            }
        }

        int comp = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j] == 1 && !check[i][j]) {
                    check[i][j] = true;
                    component[i][j] = comp;
                    dfs(i, j, comp);
                    comp += 1;
                }
            }
        }
        int ans = bfs();
        System.out.println(ans);
    }
}

 

과거에 C++로 PS를 하던 시절에 탈탈 털리고 포기했던 문제를 이번에 자바로 다시 풀었다.

처음으로 혼자 힘으로 골드3 문제를 풀어서 매우 기분이 좋다.

 

구해야 하는 것은 "가장 짧은 다리의 길이", BFS를 사용한 최단경로 문제라는 것을 알 수 있다.

 

 

int[][] map : 섬과 바다를 표시하는 지도. (이전 다리의 길이 + 1) 의 숫자를 0으로 갱신하여 바다에 다리를 올리는 것을 표현.

int[][] component : 각 섬을 구분하기 위해 사용한다. A섬에서부터 이어지기 시작한 다리 역시 A섬의 일부로 보아 A섬과 똑같은 숫자가 주어진다. 

boolean[][] check : int[][] component를 구하기 위한 DFS에서만 사용하는 체크용 배열. 이후 BFS에서는 map[i][j]==0으로 !check[i][j]를 대체한다.

 

 

핵심 아이디어는 모든 섬에서 순서대로 한 칸 씩 다리를 올려나가게 하는 것이다.

 

그렇게 한 칸 씩 차례대로 다리를 올리다 보면 다음에 다리를 올려야 하는 칸에 이미 다른 섬에서 올리고있는 다리가 존재하는 순간이 오게 된다.

 

그때 (나의 섬이 올리고있던 다리의 길이 + 다른 섬이 올리고있던 내가 만난 다리의 길이) 를 구하면 두 섬을 잇는 다리의 길이가 된다.

(이런식으로 다리의 최소값을 구하면 그게 정답이 된다.)

 

 

다른 섬의 다리를 만났다면 더이상 큐에 추가하지 않아도 된다.