[백준/G3/BFS/자바] 2146. 다리 만들기

💡 문제

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

 

여러 섬으로 이루어진 나라가 있다.

이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다.

하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다.

그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고,

그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다.

이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.

다음은 세 개의 섬으로 이루어진 나라의 지도이다.

 

 

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다.

이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.

가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다.

다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

 

 

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다

(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

 

⌨ 입력

 

첫째줄 지도의 크기 N ( 100 이하 자연수 )

map 정보 : 육지 = 1  바다 = 0

 

💻 출력 / 제한

 

첫째줄에 가장 짧은 다리의 길이를 출력한다.

 

---

풀이 방법

 

문제 유형 : BFS

제 코드의 동작 방식을 나타내 보았습니다.

까만 부분이 섬이고 파란 부분이 bfs가 동작한 모습 입니다.

노란색 줄이 최단 거리를 나타냅니다.

 

📝문제 풀이

 

문제는 섬에서 다른 섬을 잇는 가장 최소 길이를 찾고 있습니다.

모든 섬 가장자리를 구해서 가장자리에서 출발하여 현재섬에서 다른 섬으로 가는

최소 거리를 찾으면 된다고 생각 했습니다.

가장자리는 섬에 bfs를 하여 상하좌우를 확인 했을 때 map[nextX][nextY] = 0 (바다) 라면

bfs를 시작한 좌표인 map[x][y] (육지)가 가장자리가 됩니다.

 

🤔 섬을 구분 해야 합니다.

 

문제에서 요구 하는 것은 가장 자리에서 다른 섬으로 가는 거리를 구해야 합니다.

하지만 (2,2) 에서 (1,2) 가는 경우 자신의 섬인데 거리를 갱신 하게 됩니다.

모든 섬은 1인데 이렇게 되면 출발 섬을 구분 할 수 없습니다.

그레서 각 섬마다 번호를 다르게 붙이고 가장 자리에 출발 섬번호를 기록 하면 된다고 생각 했습니다.

자신의 섬이 아니고 다른섬을 만나면 거리가 갱신 되는거죠!

 

📌 섬에 번호를 붙이고 가장자리를 찾는 과정

 

Map을 돌며 map[i][j] == 1 이면 섬입니다.

섬을 발견하면 bfs를 통해 섬에 넘버링을 하고 가장자리를 찾을 수 있습니다.

bfs중 map[nextX][nextY] == 0 (육지)가 있다면 bfs를 한 map[x][y] 좌표는 가장 자리 인거죠!

색칠된 부분이 가장자리 입니다.

 

📌 최단 거리 찾는 과정

최단 거리는 bfs를 하며 도착한 곳이 바다라면 거리를 + 1 해서 큐에 넣고

섬일 경우 출발섬인지 체크하여 거리를 갱신 하고 최단 거리를 찾았으니 return; 하면 됩니다.

 

---

 

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class MakingBridge2146 {
    static ArrayList<int[]> startList;
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int num = 2, N;
    static int minLength = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][];
        startList = new ArrayList<>();

        for(int i = 0; i < map.length; i++) {
            map[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        //각 섬을 구분 하기 위해 넘버링 bfs
        for(int i = 0; i < map.length; i++){
            for(int j = 0; j < map[0].length; j++){
                if(map[i][j] == 1) {
                    bfs(i, j, false);
                    num++;
                }
            }
        }

        // 각섬의 가장 자리 bfs
        for (int[] dots : startList) {
            int x = dots[0]; int y = dots[1];
            bfs(x,y,true);
        }
        System.out.println(minLength);
    }

    static void bfs(int row, int col, boolean isFind){
        boolean[][] visited = new boolean[N][N];

        visited[row][col] = true;
        Queue<int[]> q = new LinkedList<>();

        if(!isFind) {
            q.add(new int[]{row, col});
            map[row][col] = num;
        }
        else{
            q.add(new int[]{row,col,0});
        }

        while(!q.isEmpty()){
            int[] poll = q.poll();
            int x = poll[0];
            int y = poll[1];

            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];

                boolean error = nextX < 0 || nextY < 0 || nextX > N - 1 || nextY > N - 1;

                //섬을 넘버링 하는 경우
                if (!isFind) {
                    if(!error) {
                        // 이어진 섬일 경우
                        if (!visited[nextX][nextY] && map[nextX][nextY] == 1) {
                            visited[nextX][nextY] = true;
                            map[nextX][nextY] = num;
                            q.add(new int[]{nextX, nextY});
                        }

                        // 가장 자리 인 경우
                        if (map[nextX][nextY] == 0) {
                            startList.add(new int[]{x, y});
                        }
                    }
                }
                //최단 거리 찾는 경우
                else{
                    if(!error) {
                        // 거리 이동중
                        if (!visited[nextX][nextY] && map[nextX][nextY] == 0) {
                            visited[nextX][nextY] = true;
                            int nextDist = poll[2] + 1;
                            q.add(new int[]{nextX, nextY, nextDist});
                        }
                        // 도착한 곳이 출발지X, map[nextX][nextY] != 0 -> 다른 섬 일경우
                        else if (map[nextX][nextY] != map[row][col] && map[nextX][nextY] != 0) {
                            minLength = Math.min(minLength, poll[2]);
                            //BFS 단계별 거리가 1씩 늘어 나는데 도착 하면 그 거리가 최단 거리 이다.
                            return;
                        }
                    }
                }
            }
        }
    }
}