백준 2146 다리 만들기 - JAVA

2146 문제 링크

---

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

 

 

문제 설명

---

 

 

입출력

---

 

코드

---

< MultiSource-BFS >

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static int minDist = Integer.MAX_VALUE;
    static int[][] map;
    static int[][] set;
    static Queue<int[]> border = new ArrayDeque<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        set = new int[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 idx = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && set[i][j] == 0) {
                    checkIsland(i, j, idx++);
                }
            }
        }
        checkMinDist();
        bw.write(String.valueOf(minDist));
        bw.flush();
    }
    private static void checkIsland(int x, int y, int idx) {
        set[x][y] = idx;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {x, y});
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            boolean isBorder = false;
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (map[nx][ny] == 0) isBorder = true;
                if (set[nx][ny] == 0 && map[nx][ny] == 1) {
                    set[nx][ny] = idx;
                    queue.offer(new int[] {nx, ny});
                }
            }
            if (isBorder) border.add(new int[] {cur[0], cur[1]});
        }
    }
    private static void checkMinDist() {
        int[][] dist = new int[N][N];
        while(!border.isEmpty()) {
            int[] cur = border.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (map[nx][ny] == 0 && set[nx][ny] == 0) {
                    set[nx][ny] = set[x][y];
                    dist[nx][ny] = dist[x][y] + 1;
                    border.offer(new int[] {nx, ny});
                } else if (set[nx][ny] != set[x][y]) { // 다른 섬 번호
                    // dist[x][y] = BFS가 진행중인 섬에서 온거리
                    // dist[nx][ny] = 다른 섬에서 이미 확장한 거리
                    minDist = Math.min(minDist, dist[x][y] + dist[nx][ny]);
                    if (minDist == 1) return;
                }
            }
        }
    }
}

 

< 단독 BFS >

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static int minDist = Integer.MAX_VALUE;
    static int[][] map;
    static boolean[][] visited;
    static List<int[]> borders = new ArrayList<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = 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 idx = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    checkIsland(i, j, idx++);
                }
            }
        }
        for (int[] border : borders) {
            checkMinDist(border);
        }
        bw.write(String.valueOf(minDist));
        bw.flush();
    }
    private static void checkIsland(int x, int y, int idx) {
        visited[x][y] = true;
        map[x][y] = idx;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {x, y});
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            boolean isBorder = false;
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (map[nx][ny] == 0) isBorder = true;
                if (!visited[nx][ny] && map[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    map[nx][ny] = idx;
                    queue.offer(new int[] {nx, ny});
                }
            }
            if (isBorder) borders.add(new int[] {cur[0], cur[1], idx, 0});
        }
    }
    private static void checkMinDist(int[] border) {
        boolean[][] visitedSea = new boolean[N][N];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(border);
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (map[nx][ny] == 0 && !visitedSea[nx][ny]) {
                    visitedSea[nx][ny] = true;
                    queue.offer(new int[] {nx, ny, cur[2], cur[3] + 1});
                } else if (map[nx][ny] != 0 && map[nx][ny] != cur[2]) {
                    minDist = Math.min(minDist, cur[3]);
                    return;
                }
            }
        }
    }
}

 

알고리즘 설명

---

해당 문제는, 구분된 섬들을 인덱스로 라벨링하고, 섬 간의 최소거리를 구하는 문제입니다. 각 섬을 라벨
섬을 라벨링한 뒤 각 섬의 경계에서 다른 섬까지의 최소 거리를 구하는 문제는 크게 두 가지 방식으로 구현할 수 있습니다.

하나는 각 경계점마다 독립적으로 BFS를 수행하는 단독BFS 방식이고, 다른 하나는 모든 경계점을 큐에 넣고 한 번의 BFS를 수행하는 멀티소스BFS 방식입니다.

 

먼저, 단독BFS를 각 섬마다 반복하는 방식은 섬의 경계점으로부터 다른 섬에 닿을때까지 BFS를 수행하는 것을 섬의 개수만큼 반복하기에 섬의 개수가 많아질수록 BFS의 호출횟수도 같이 증가합니다. 또한, 단독BFS로는 모든 섬에서 BFS를 수행해야 하기에, A섬에서 시작해서 B섬까지 거리를 A섬시작 BFS(A -> B), B섬시작 BFS(B -> A)와 같이 불필요한 중복연산이 수행되는 것을 알 수 있습니다. 또한, 섬 별로 수행할 BFS에 N*N크기의 방문 배열을 새로 생성해야 하므로 섬의 개수 * N^2의 추가 메모리를 소모하게 됩니다. 즉, 섬이 많아질수록 시간과 공간이 모두 비효율적으로 증가하는 구조라는 것을 알 수 있습니다.

 

반면, 멀티소스 BFS는 모든 섬의 경계점을 한 큐에 넣고 동시에 확장해 나가기 때문에 전체 지도에 대해 단 한 번의 BFS만 수행됩니다. 여러 출발점이 한꺼번에 퍼져 나가며 서로 다른 섬의 확장 경로가 처음으로 맞닿는 지점이 곧 최단거리이므로, A -> B와 B -> A처럼 대칭되는 중복 연산도 발생하지 않습니다. 따라서, 시간복잡도는 사실상 O(N^2)로 고정되며, 방문배열 역시 한 번만 생성되므로 메모리 사용량 또한 최소화 할 수 있는 것을 알 수 있습니다.

 

결국, 단독 BFS는 섬이 많고 경계가 많은 경우 연산량과 메모리 사용량이 급격하게 증가하는 반면, 멀티소스BFS는 전체 맵크기에 대한 단일 BFS와 하나의 방문배열로 문제를 해결할 수 있어 훨씬 효율적이라는 것을 알 수 있습니다.

아래는 멀티소스BFS와 섬 별 단독BFS의 소요시간 차이입니다.

위부터 차례대로 멀티소스BFS, 단독BFS

 

코드 해석

---

입력받은 map[][]을 index를 활용해 4방위 BFS 탐색을 진행하면서 map[nx][ny]가 0(섬의 경계)이라면 경계를 저장하는 border큐에 넣어주고, set[nx][ny]가 0(미방문 상태)이면서 map[nx][ny]가 1(육지)라면 set[nx][ny]에 index번호를 넣어 각 섬을 index로 구분합니다.

 

이후 border 큐에 모든 섬들의 경계좌표가 들어있으므로, 그대로 BFS를 진행하는데, map[nx][ny]가 0(바다)이면서 set[nx][ny]가 0(아직 어떤 섬에도 속하지 않은 바다)인 경우에는 해당 바다 칸(set[][])을 현재 섬 번호를 넣어 확장하고, dist[nx][ny]를 dist[x][y] + 1로 업데이트하며 현재 섬에서 확장된 거리를 기록합니다.

 

큐 특성상 각 섬의 거리별로 동시에 퍼져나가므로, 만약 set[nx][ny]가 현재 섬의 번호 set[x][y]와 다르다면 이는 서로 다른 섬의 확장 영역이 맞닿아있다는 의미가 됩니다.

 

따라서 dist[x][y]는 현재 탐색중인 섬의 경계부터 좌표(x, y)까지의 최단거리이고, dist[nx][ny]는 이미 다른 섬의 경계부터 좌표(nx, ny)까지의 최단거리이기 때문에, dist[x][y] + dist[nx][ny]는 두 섬의 최단거리임을 알 수 있습니다.

 

그리고 각 섬들 간의 최단거리를 비교해서 가장 짧은 최단거리를 반환해야 하므로, minDist를 Math.min()을 활용하여 가장 짧은 최단거리를 반환합니다.