[JAVA] 백준 2146번: 다리 만들기 ( 초급 2-48 ) - fail

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

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

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

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

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

입력

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

출력

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

 

문제 풀이

간척사업을 진행한다고 생각하면 된다.

1.  섬과 바다를 구분하는 어레이를 만든다. (문제의 입력 값을 저장)

2. 각각의 섬을 구분할 수 있는 어레이를 만든다. ( terrytoryInfo 에 저장하였다. )

3. 각각의 섬 가장 자리로 부터 떨어지는 거리의 값을 저장한 어레이를 만든다. ( distInfo )

4. 모든 섬을 큐에 집어 넣는다.

5. bfs 실행

6. 큐에서 좌표를 하나씩 꺼내고 상, 하, 좌, 우로 살핀다.

7. 방문하지 않은 바다에 도착한 경우, 현재 좌표에 이전 영토 정보를 저장하고, 이전 영토와의 거리 +1을 저장

8. 방문한 바다에 도착한 경우, 이전 좌표에서의 영토와의 거리와, 현재 좌표에서의 영토와의 거리를 더한 값을 결과 리스트에 저장한다.

9. 결과 리스트에서 최소 값을 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon2146_2 {
    private static int n;
    private static int[][] info;
    private static boolean[][] visit;
    private static int[][] distInfo;
    private static int[][] territoryInfo;
    private static int[] rowTemp = { -1, 1, 0, 0 };
    private static int[] colTemp = { 0, 0, -1, 1 };
    private static ArrayList<Integer> result = new ArrayList<>();

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        info = new int[n][n];
        visit = new boolean[n][n];
        distInfo = new int[n][n];
        territoryInfo = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                info[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        // 영토인 좌표를 모두 큐에 집어 넣는다.
        Queue<Position2146> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (info[i][j] == 1) {
                    queue.add(new Position2146(i, j));
                }
            }
        }
		
        // 각각 다른 영토임을 구분할 수 있는 어레이를 만들고, 안에 결과값을 집어 넣는다.
        int terriyToryNumber = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && info[i][j] == 1) {
                    setTerritoryInfo(i, j, terriyToryNumber);
                    territoryInfo[i][j] = terriyToryNumber;
                    terriyToryNumber++;
                }
            }
        }
		
        // 다리를 만들 수 있는 모든 결과 값을 result라는 리스트에 집어 넣는다.
        findMinimumDistance(queue);
        System.out.println(Collections.min(result));
    }

    private static void setTerritoryInfo(int row, int col, int terriyToryNumber) {
        Queue<Position2146> q = new LinkedList<>();
        q.add(new Position2146(row, col));

        while (!q.isEmpty()) {
            Position2146 position = q.remove();
            int currentRow = position.row;
            int currentCol = position.col;

            for (int i = 0; i < 4; i++) {
                int nextRow = currentRow + rowTemp[i];
                int nextCol = currentCol + colTemp[i];
                if (nextRow >= 0 && nextCol >= 0 && nextRow < n && nextCol < n) {
                    if (!visit[nextRow][nextCol] && info[nextRow][nextCol] == 1) {
                        visit[nextRow][nextCol] = true;
                        territoryInfo[nextRow][nextCol] = terriyToryNumber;
                        q.add(new Position2146(nextRow, nextCol));
                    }
                }
            }
        }
    }

    private static void findMinimumDistance(Queue<Position2146> queue) {
        while (!queue.isEmpty()) {
            Position2146 position = queue.remove();
            int currentRow = position.row;
            int currentCol = position.col;

            for (int i = 0; i < 4; i++) {
                int nextRow = currentRow + rowTemp[i];
                int nextCol = currentCol + colTemp[i];

                if (nextRow >= 0 && nextCol >= 0 && nextRow < n && nextCol < n) {
                    if (!visit[nextRow][nextCol]) {
                        visit[nextRow][nextCol] = true;
                        distInfo[nextRow][nextCol] = distInfo[currentRow][currentCol] + 1;
                        territoryInfo[nextRow][nextCol] = territoryInfo[currentRow][currentCol];
                        queue.add(new Position2146(nextRow, nextCol));
                    } else if (info[nextRow][nextCol] == 0
                            && territoryInfo[nextRow][nextCol] != territoryInfo[currentRow][currentCol]) {
                        result.add(distInfo[nextRow][nextCol] + distInfo[currentRow][currentCol]);
                    }
                }
            }
        }
    }
}

class Position2146 {
    int row;
    int col;

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