백준 - 2146 다리 만들기(Java)

bfs 문제입니다.

 

서로 다른 섬을 연결하는 최소 간선의 비용을 구하는 문제입니다.

다리를 만들 수 있는 방법은 많지만, 최소 간선을 보장해야 하기 때문에 bfs를 써야 한다는 것을 알 수 있습니다.

 

문제 접근 방법은 다음과 같습니다.

1. 탐색을 하여 같은 섬일 경우 넘버링을 동일하게 한다.(dfs)
2. 바다인 곳을 탐색하면서 다른 섬에 도착하면 탐색을 멈춘다.(bfs)

💡 1번 넘버링의 경우 dfs, bfs 둘 중 아무거나 해도 상관 없습니다.

그림과 같이 넘버링을 통해 같은섬인지 아닌지 확인합니다.

같은 섬이 아닐경우(바다 or 다른 섬)를 bfs로 진행하시면 됩니다.

 

[구현 코드]

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int n, min;
    private static int[][] map, islands;
    private static boolean[][] mapVisited;
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    private static class Node{
        int x, y, depth;

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

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

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        islands = new int[n][n];
        mapVisited = new boolean[n][n];

        for(int i=0; i<n; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());
            }
        }

        // 같은 섬을 넘버링함
        int cnt = 1;
        for(int i=0; i<n; i++) {
            for (int j = 0; j < n; j++) {
                if(map[i][j] == 1 && !mapVisited[i][j]){
                   findSameIsland(i, j, cnt++);
                }
            }
        }

        min = Integer.MAX_VALUE;
        for(int i=0; i<n; i++){
            for (int j = 0; j < n; j++) {
                if(islands[i][j] >= 1){
                    mapVisited = new boolean[n][n];
                    bfs(i, j, islands[i][j]);
                }
            }
        }

        bw.write(String.valueOf(min-1));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs(int x, int y, int type){
        Queue<Node> qu = new LinkedList<>();
        qu.add(new Node(x, y, 0));

        while (!qu.isEmpty()) {
            Node cn = qu.poll();

            // 다른 섬일경우
            if(islands[cn.x][cn.y] != type && islands[cn.x][cn.y] > 0){
                min = Math.min(min, cn.depth);
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cn.x + dx[i];
                int ny = cn.y + dy[i];

                if (!(nx >= 0 && ny >= 0 && nx < n && ny < n)) continue;
                if (mapVisited[nx][ny] && islands[nx][ny] == 0) continue;

                if(islands[nx][ny] != type){
                    mapVisited[nx][ny] = true;
                    qu.add(new Node(nx, ny, cn.depth+1));
                }
            }
        }
    }

    // dfs를 통한 넘버링
    private static void findSameIsland(int x, int y, int cnt) {
        islands[x][y] = cnt;
        mapVisited[x][y] = true;

        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(mapVisited[nx][ny]) continue;

            if(map[nx][ny] == 1){
                findSameIsland(nx, ny, cnt);
            }
        }
    }
}