250x250
06-26 10:56
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DFS, BFS, 시뮬, 백트래킹

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

막무가내막내 2021. 3. 1. 17:18
300x250
SMALL

 

 

www.acmicpc.net/problem/2146

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

 

 

 

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

}

 

 

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

 

 

300x250
LIST
"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."
0 Comments
댓글쓰기 폼