[알고리즘] 백준 2146 다리만들기 -BFS- 자바

 

 

www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

 

 

백준 BFS 유형의 백준 2146 다리만들기 문제입니다.

여러개의 섬이(1) 있는데 바다에(0) 최소의 다리 개수를 설치하여 여러개의 섬들 중 두 개의 섬을 이을 수 있게 하려는 문제 입니다.

BFS를 살짝 응용한 문제입니다. 처음에 너무 비효율적으로 자원을 소비하는건가 했는데 통과되었습니다. 

 

 

풀이를 간략히 설명하면, 

 

1. 섬마다 번호가 똑같으므로 바로 BFS로 다른 섬을 찾아 연결하기가 힘듭니다. 그러므로 섬에 각각 다른 번호이름을 붙여주도록 합니다.

 

2. 이제 섬마다 BFS를 하여 다른 섬과 다리를 설치할 수 있는 경우의 수를 찾도록 합니다. 그리고 다리를 최소의 개수로 설치한 경우를 업데이트 해줍니다.

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    private static int[][] map;
    private static boolean[][] isVisited;
    private static int N;
    private static int[] dr = new int[]{-1, 0, 1, 0};
    private static int[] dc = new int[]{0, -1, 0, 1};
    private static int landNum = 2; //섬 번호이름
    private static int answer = Integer.MAX_VALUE; //답

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        isVisited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (map[r][c] == 1) { // 아직 번호이름 없는 섬인 경우
                    makeLand(r, c);
                }
            }
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (map[r][c] >= 2) {
                    isVisited = new boolean[N][N]; //재초기화
                    bfs(r, c);
                }
            }
        }
        System.out.println(answer);
    }

    // 섬 별로 번호이름 붙여주기
    private static void makeLand(int r, int c) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r, c, 0));
        isVisited[r][c] = true;
        map[r][c] = landNum;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if ((r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) && !isVisited[r2][c2] && map[r2][c2] == 1) {
                    isVisited[r2][c2] = true;
                    map[r2][c2] = landNum;
                    queue.offer(new Point(r2, c2, 0));
                }
            }
        }
        landNum++;
    }

    private static void bfs(int r, int c) {
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(r, c, 0));
        int currentLandNum = map[r][c];// 현재 섬 번호
        isVisited[r][c] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if ((r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) && !isVisited[r2][c2] && map[r2][c2] != currentLandNum) { //방문안하고 바다 혹은 다른 섬인 경우
                    isVisited[r2][c2] = true;
                    if (map[r2][c2] == 0) { //바다
                        queue.offer(new Point(r2, c2, point.cnt + 1));
                    } else { //다른 섬
                        answer = Math.min(answer, point.cnt);
                    }
                }
            }
        }
    }

    static class Point {
        int r;
        int c;
        int cnt;

        public Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }

}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!