[BOJ 2146]ブリッジ(Java)

31835 ワード
白駿 BFS テキストリンク

質問する


多くの島からなる国がある.この国の大統領は島をつなぐ橋を作る公約で人気を集め、当選した.しかし、彼が本当に大統領に就任したとき、私は彼が橋を架けるのが惜しいと思った.そこで、彼は1つの島と別の島を結ぶ橋を目立つように建設し、橋を最も短くしてお金を節約することにした.
この国はN×Nサイズの2 D平面上に存在します.この国は多くの島からなり、島は東西南北の陸地がつながっているブロックを指す.次は三つの島からなる国の地図です.

上図の色の部分は陸地で、無色の部分は海です.この海に一番短い橋を架けて二つの大陸をつなぎたい.最も短い橋とは、橋がメッシュの中で占める格子数が最も小さい橋を指す.下の図から2つの大陸を結ぶ橋が見えます.

もちろん、上記の方法以外にも多くの架橋方法がありますが、上記の場合、架橋の長さは最短で3となります(もちろん、架橋3の他にもいくつかの方法があります).
地図が与えられたとき、最も短い橋を置いて、2つの大陸を結ぶ方法を探します.

方法


  • 陸地と海洋に分け、BFSで陸地ごとに固有のエリア数を設定します.

  • すべてのノードに移動し、アクセスされていない領域にアクセスすると、BFSによってその領域の座標に移動し、一意の領域数に基づいて最も近い位置の領域に移動します.

  • 新しい領域に遭遇した場合、静的距離値が更新されます.

    • ソースコード

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

    結果


    vimメモ
    LeetCode: Remove Element