[BOJ 2146] 다리 만들기 (Java)

문제

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

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

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

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

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

접근 방법

1. 육지와 바다로 나뉘어져 있어 BFS로 육지마다 고유의 지역 숫자를 설정해줍니다.

2. 모든 노드를 탐색하며 방문하지 않은 지역을 접근하면 해당 지역의 좌표와 고유의 지역 숫자를 바탕으로 가장 가까운 위치에 있는 지역까지 BFS를 통해 탐색합니다.

3. 새로운 지역을 만나면 static에 올라와 있는 distance 값을 갱신합니다.

소스 코드

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

public class MakeBridge {

    static int n;
    static int[][] graph;
    static int distance = Integer.MAX_VALUE;
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};

    static class Node {
        int x;
        int y;
        int move;

        public Node(int x, int y, int move) {
            this.x = x;
            this.y = y;
            this.move = move;
        }
    }

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

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(input[j]);
            }
        }

        int regions = regionNumbering(); // 지역 개수
        boolean[] visitedRegion = new boolean[regions]; // regions 는 실제보다 1 크다

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] != 0 && !visitedRegion[graph[i][j]]) {
                    visitedRegion[graph[i][j]] = true;
                    findShortest(graph[i][j], i, j);
                }
            }
        }

        System.out.println(distance);
    }

    // region Number 지역으로부터 가장 짧은 거리를 가지는 region 을 return
    public static void findShortest(int regionNumber, int regionX, int regionY) {
        ArrayDeque<Node> dq = new ArrayDeque<>();
        boolean[][] visit = new boolean[n][n];

        dq.offerLast(new Node(regionX, regionY, 0));
        visit[regionX][regionY] = true;

        while (!dq.isEmpty()) {
            Node now = dq.removeFirst();
            if (now.move >= distance) {
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int tmpx = now.x + dx[i];
                int tmpy = now.y + dy[i];
                if (0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < n && !visit[tmpx][tmpy]) {
                    if (graph[tmpx][tmpy] == regionNumber) {
                        dq.offerLast(new Node(tmpx, tmpy, 0));
                        visit[tmpx][tmpy] = true;
                    } else if (graph[tmpx][tmpy] == 0) {
                        dq.offerLast(new Node(tmpx, tmpy, now.move + 1));
                        visit[tmpx][tmpy] = true;
                    } else {
                        distance = Math.min(now.move, distance);
                    }
                }
            }
        }
    }

    public static int regionNumbering() {
        ArrayDeque<Node> dq = new ArrayDeque<>();
        boolean[][] visit = new boolean[n][n];
        int cur = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && graph[i][j] != 0) {
                    dq.offerLast(new Node(i, j, 0));
                    graph[i][j] = cur;
                    visit[i][j] = true;

                    while (!dq.isEmpty()) {
                        Node now = dq.removeFirst();
                        for (int k = 0; k < 4; k++) {
                            int tmpx = now.x + dx[k];
                            int tmpy = now.y + dy[k];
                            if (0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < n && !visit[tmpx][tmpy] && graph[tmpx][tmpy] != 0) {
                                graph[tmpx][tmpy] = cur;
                                visit[tmpx][tmpy] = true;
                                dq.offerLast(new Node(tmpx, tmpy, 0));
                            }
                        }
                    }
                    cur++;
                }
            }
        }
        return cur;
    }
}

결과