[백준] 다리 만들기 (2146) Java

문제 링크

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

2146번: 다리 만들기

 

문제 요약

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 섬을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 섬을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

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

 

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

 

출력

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

 

접근법

알고리즘 문제를 어느정도 풀어봤다면, 2차원 격자에서 임의의 모양의 구역(이 문제에선 섬)을 구분 짓는 방법? 그 구역을 구하는 방법?에 대해서 이미 잘 알고 있을 것이다.

각 섬의 임의의 한 지점에서 BFS로 방문 표시를 해가며 구역의 경계선까지 전부 탐색을 하면 된다.

 

그래서 이 문제에서는 최소 다리의 길이를 구하는 아이디어만 떠올리면 되는데, 이 역시 그리 어렵지 않다.

 

격자 위의 임의의 두 육지를 선택했을 때, 두 육지 사이에 지을 수 있는 다리의 최소 길이는 다음과 같다.

위 격자에서 파란 지점에서 주황색 지점으로 최소 길이로 다리를 놓는다고 했을 때, 선으로 그려놓은 것 처럼 여러가지 경우의 수가 있다.

그런데 중요한 것은 각 선이 지나가는 지점의 개수가 전부 4칸으로,

이는 파란 지점과 주황색 지점의 맨해튼 거리에서 1을 뺀 값이다.

 

맨해튼 거리는 | x2 - x1 | + | y2 - y1 | 인데 (뭔지 잘 모르겠으면 구글링을 해보면 쉽게 알 수 있다. 별거 아니다)

이는 두 지점이 위 격자에서 가로로 떨어져 있는 칸의 개수 + 세로로 떨어져 있는 칸의 개수를 더한 값이다. 그냥 당연한 소리다.

 

근데 결국에는 이 가로로 떨어진 거리와 세로로 떨어진 거리 만큼 다리를 지어야 두 지점을 이을 수 있다는 것이다.

 

그런데 여기서 주의해야 할 점은 이 다리는 육지 위까지 짓는 것이 아니라, 육지와 바로 인접한 바다까지만 지으면 된다는 것이다.

따라서 두 지점 사이의 다리 길이의 최소값은, 두 지점 사이의 맨해튼 거리에서 1을 뺀 값이 된다.

 

설명을 하기가 어려워서 그렇지, 그냥 사실 당연한 소리다. 그래도 설명에 책임감을 느끼며 수식으로 표현하면

임의의 두 지점 사이의 가로로 떨어진 거리가 X, 세로로 떨어진 거리가 Y라고 했을 때 맨해튼 거리는 X + Y 이다.

 

두 지점 사이에 최소 길이로 다리를 짓는다고 했을 때 매우 다양한 경우가 있지만 (위의 그림을 잘 보면서 생각을 해보자)

결국엔 다리가 가로로 놓여진 길이가 X이고 세로로 놓여진 길이가 Y - 1인 경우와,

가로로 놓여진 길이가 X - 1 이고 세로로 놓여진 길이가 Y인 두 경우밖에 없다.

 

그래서 결국에는 각 섬에 대해서 모든 육지 좌표를 ArrayList로 저장한다. 섬이 여러개이므로 ArrayList<ArrayList> 형태로 모든 섬에 대해서 저장을 한다.

 

그리고 가능한 모든 두 섬의 조합에 대해서

한 섬에서 육지 하나를 뽑고, 다른 한 섬에서 육지 하나를 뽑아서 두 육지 사이의 맨해튼 거리 - 1의 최솟값을 구한다.

그리고 그 최솟값들 중에서 다시 최솟값을 구하는 것이다.

 

이렇게 되면 바다에 인접하지 않은 육지 사이 (다리를 지을 수 없는 경우) 에도 거리가 구해지는데, 이 경우는 최솟값을 구할 때 알아서 제외되므로 상관 없음을 직관적으로 알 수 있다.

 

원한다면 최적화를 해서 각 섬의 육지 좌표를 저장할 때 바다에 인접한 육지의 좌표만 저장해도 된다. 나는 그렇게 풀었다.

최적화를 안 한 경우와의 시간 차이는 100ms 이내로 크지 않았다.

 

 

시간 복잡도

모든 섬의 육지 정보를 저장하는 데 O(N^2). N이 최대 100이므로 크지 않다.

모든 육지 사이의 맨해튼 거리를 구하는 데는 그래도 어느정도 시간이 들 텐데, 섬의 개수라던가 여러가지 고려할 점이 많아서 이 부분에서는 시간 복잡도 계산이 어렵다. 아무튼 N이 크지 않아서, 최적화를 하지 않아도 500ms 안에 문제가 풀린다.

 

 

공간 복잡도

지도: char * N^2

섬 육지 좌표: int * 2 * N^2 (섬이 2개 이상이므로 바다가 존재하기 때문에 이 값보다는 조금 작다)

visit 배열: boolean * N^2

N이 작으므로 고려할 필요 없다.

 

 

풀면서 놓쳤던 점

딱히 없다.

 

 

이 문제에서 얻어갈 점

BFS. 맨해튼 거리의 사용.

 

 

코드

import java.io.*;
import java.util.*;

/* https://kloong.tistory.com/entry/백준-다리-만들기-2146-Java */

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int len = Integer.parseInt(br.readLine());

        char[][] map = new char[len][len];

        //입력받은 map을 char[][] 형태로 공백 없이 저장
        readMap(map, br);

        //모든 섬의 육지 좌표를 저장하는 list
        //각각의 ArrayList<Ground>에는 한 섬의 육지의 좌표가 저장되어 있음
        ArrayList<ArrayList<Ground>> islandList = new ArrayList<>();

        //BFS를 통해 모든 섬의 육지 좌표를 저장함.
        findAllIslands(map, islandList);

        //모든 가능한 두개의 섬의 조합을 선택해서
        //각 조합마다 최소 다리 길이를 측정하고, 모든 조합에 대해서 최소값을 반환하는 함수
        System.out.println(getMinBridgeLength(islandList));
    }

    static void findAllIslands(char[][] map, ArrayList<ArrayList<Ground>> islandList)
    {
        //bfs에 쓰일 visit 배열
        boolean[][] visit = new boolean[map.length][map.length];

        //map의 모든 공간을 차례로 탐색
        for (int row = 0; row < map.length; row++)
        {
            for (int col = 0; col < map.length; col++)
            {
                if (map[row][col] != '1' || visit[row][col])
                    continue;

                //바다가 아니고, 방문한 적이 없는 육지를 만나면 bfs 시작
                //이 육지를 시작점으로 bfs를 하므로, 이 육지에 대한 객체를 넘겨줌
                //bfs를 해서 얻어낸 섬의 모든 육지를 ArrayList<Ground> 형태로 반환하는 함수임
                islandList.add(getGroundListOfIsland(map, new Ground(row, col), visit));
            }
        }
    }

    static ArrayList<Ground> getGroundListOfIsland(char[][] map, Ground startGround, boolean[][] visit)
    {
        //반환해줄 함수. 섬의 모든 육지 좌표를 저장한다. 시작이 될 육지를 미리 넣어줌
        ArrayList<Ground> groundList = new ArrayList<>();
        groundList.add(startGround);

        //각 육지의 상하좌우를 탐색하기 편하게 하기 위한 방향 배열
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        //bfs를 위한 queue와 queue의 초기화
        Queue<Ground> bfsQueue = new LinkedList<>();
        bfsQueue.add(startGround);
        visit[startGround.row][startGround.col] = true;

        //bfs
        Ground pivot, neighborGround;
        int neighborRow, neighborCol;
        while (!bfsQueue.isEmpty())
        {
            pivot = bfsQueue.poll();

            for (int[] dir : dirs)
            {
                neighborRow = pivot.row + dir[0];
                neighborCol = pivot.col + dir[1];

                //pill한 육지와 이웃한 육지가 map 안에 있는지, 바다가 아닌지, 방문한적 없는지 체크
                if (!isInMap(neighborRow, neighborCol, map.length) ||
                        map[neighborRow][neighborCol] != '1' ||
                        visit[neighborRow][neighborCol])
                    continue;

                visit[neighborRow][neighborCol] = true;

                neighborGround = new Ground(neighborRow, neighborCol);
                bfsQueue.add(neighborGround);

                //반환해 줄 arrayList에도 add해줘야 한다.
                //바다에 인접한 육지에만 다리를 지을 수 있으므로,
                //바다에 인접한 육지만 arraylist에 add한다.
                if (canBuildBridge(neighborGround, map, dirs))
                    groundList.add(neighborGround);
            }
        }

        return groundList;
    }

    //islandList의 모든 섬에 대해서 최소 다리 길이를 반환하는 함수
    static int getMinBridgeLength(ArrayList<ArrayList<Ground>> islandList)
    {
        int minBridgeLen = Integer.MAX_VALUE;

        ArrayList<Ground> pivotIsland, otherIsland;

        for (int pivot = 0; pivot < islandList.size() - 1; pivot++)
        {
            pivotIsland = islandList.get(pivot);
            for (int idx = pivot + 1; idx < islandList.size(); idx++)
            {
                otherIsland = islandList.get(idx);

                //섬 두개를 뽑는 모든 조합에 대해서 다리 길이를 구함.
                //그 중 최소 길이를 저장한다.
                minBridgeLen = Math.min(minBridgeLen, getMinBridgeLength(pivotIsland, otherIsland));
            }
        }

        return minBridgeLen;
    }

    //각 섬에서 육지 하나씩을 뽑는 모든 조합에 대해서 맨해튼 거리를 구함
    //최소 맨해튼 거리 - 1 을 반환함. 다리를 지을 때는 육지 바로 옆에 지어야 하기 떄문.
    static int getMinBridgeLength(ArrayList<Ground> island1, ArrayList<Ground> island2)
    {
        int minBridgeLen = Integer.MAX_VALUE;

        for (Ground g1 : island1)
        {
            for (Ground g2: island2)
            {
                minBridgeLen = Math.min(minBridgeLen, g1.getManhattanDistTo(g2) - 1);
            }
        }

        return minBridgeLen;
    }

    static boolean isInMap(int row, int col, int len)
    {
        return row >= 0 && row < len && col >= 0 && col < len;
    }

    static boolean canBuildBridge(Ground g, char[][] map, int[][] dirs)
    {
        int neighborRow, neighborCol;

        for (int[] dir : dirs)
        {
            neighborRow = g.row + dir[0];
            neighborCol = g.col + dir[1];

            if (!isInMap(neighborRow, neighborCol, map.length))
                continue;

            //바다와 인접해 있는 육지인 경우를 찾는다.
            //섬 내부에 바다가 있어서 다리를 건설하지 못하지만 true를 반환할 수 있긴 한데
            //어차피 최소값을 구하기 때문에 이 경우는 최종 정답에서 걸러질 수밖에 없다
            if (map[neighborRow][neighborCol] == '0')
                return true;
        }

        return false;
    }

    static void readMap(char[][] map, BufferedReader br) throws IOException
    {
        String row;
        for (int i = 0; i < map.length; i++)
        {
            row = br.readLine();
            for (int j = 0; j < map.length; j++)
                map[i][j] = row.charAt(j * 2); //입력 주의. 사이사이 공백 있음.
        }
    }
}

class Ground
{
    int row;
    int col;

    Ground(int row, int col)
    {
        this.row = row;
        this.col = col;
    }

    int getManhattanDistTo(Ground other)
    {
        return Math.abs(other.row - this.row) + Math.abs(other.col - this.col);
    }
}