(백준) 다리만들기 - 2146

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

모든섬들에 대해서 자신을 제외한 모든 섬들에 대한 다리를 만들고 최소값을 비교하면 최대 섬의 개수 100개일 경우 100 * 99 .. 로 100!의 경우가 나온다.

따라서 이러한 방법이 아니라 100개의 섬에 대해서 각각 다른 섬을 찾으면서 다리를 놓다가 아무 섬이든 닿으면 최단거리 다리길이 값을 갱신하고 이 이상값이 나올경우 제외하는 방법으로 하면 더 빠르게 풀수 있다.

참고로 최단 거리다리를 찾아야하므로 우선순위 큐를 이용했다.

---

설명

먼저 100 x 100 맵을 돌면서 모든 섬을 체크해준다. 이때 해당 섬들에게 고유 번호를 매겼다.

섬의 개수 만큼 섬의 방문 체크를 위한 일차원 배열 island를 생성하고, 다시 맵을 순회하면서방문한 섬이 아닌 경우 섬 내부 이동의 경우 거리값을 0으로 초기화하고, 바다로 넘어가는 경우 +1 해주면서 다리를 지었다.

이렇게 다른 섬에 도달하면 최소값을 갱신하고, 이후 부턴 최소값보다 커지는 경우에 대해서는 전부 제외하도록 했다.

 

코드

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

public class Main {
    static int N, MIN_DIST = Integer.MAX_VALUE;
    static int[][] board;
    static boolean[][] visited;
    static boolean[] island;
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++)
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int indexing = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && board[i][j] == 1) {
                    visited[i][j] = true;
                    board[i][j] = ++indexing;
                    findAllIsland(new Dot(i, j), indexing); // 섬 찾고 인덱싱
                }
            }
        }

        island = new boolean[indexing+1]; // 섬에 대한 방문 체크
        visited = new boolean[N][N]; // 각 섬에서 다른 섬을 찾을 때 사용하는 방문체크

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!island[board[i][j]] && board[i][j] >= 1) {
                    island[board[i][j]] = true;
                    findMinDistIsland(new Dot(i, j), board[i][j]); // 다른 섬까지의 최단거리를 구한다
                    visited = new boolean[N][N]; // 각 섬이 끝나면 초기화
                }
            }
        }
        System.out.println(MIN_DIST);
    }

    private static void findMinDistIsland(Dot dot, int nowIsland) {
        PriorityQueue<Dot> queue = new PriorityQueue<>(Comparator.comparingInt(d -> d.d));
        visited[dot.i][dot.j] = true;
        queue.add(dot);

        while (!queue.isEmpty()) {
            Dot now = queue.poll();

            for (int d = 0; d < 4; d++) {
                int ny = now.i + dy[d];
                int nx = now.j + dx[d];

                 // *중요* BFS로 값을 구할 때는 Queue에 넣기전에 예외값들을 모두 제외 처리해줘야 한다
                if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
                if (visited[ny][nx]) continue;
                if (now.d >= MIN_DIST) continue;
                visited[ny][nx] = true;

                if (board[ny][nx] == nowIsland) queue.add(new Dot(ny, nx, 0));
                else if (board[ny][nx] == 0) queue.add(new Dot(ny, nx, now.d + 1));
                else MIN_DIST = now.d;
            }
        }
    }

    private static void findAllIsland(Dot dot, int idx) {
        Queue<Dot> queue = new LinkedList<>();
        queue.add(dot);

        while (!queue.isEmpty()) {
            Dot now = queue.poll();

            for (int d = 0; d < 4; d++) {
                int ny = now.i + dy[d];
                int nx = now.j + dx[d];

                if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
                if (visited[ny][nx]) continue;
                if (board[ny][nx] == 0) continue;

                visited[ny][nx] = true;
                board[ny][nx] = idx;
                queue.add(new Dot(ny, nx));
            }
        }
    }

    private static class Dot {
        int i, j, d = 0;
        public Dot(int i, int j) {
            this.i = i;
            this.j = j;
        }
        public Dot(int i, int j, int d) {
            this.i = i;
            this.j = j;
            this.d = d;
        }
    }
}