87. 다리 만들기 (백준 2146) [JAVA]

 

문제

문제 링크 : https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	192MB	23035	8150	5099	33.218%

문제

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

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

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

입력

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

출력

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

 

풀이

우선 중요한 섬을 구분지어야 여기가 같은 섬인지, 다른 섬인지 알 수 있기 때문에 전체 지도에서 여러 번 BFS를 사용하여 각각 섬을 색칠하였다.

이때 해시맵에다 각각의 섬에서의 가장자리 좌표만 큐에 따로 저장하였다.

이 가장자리 좌표들에서 다시 BFS를 통해 각 섬에서 -> 다른 섬까지의 최단경로를 계산할 것이다.

각각의 섬들에 대해서 BFS를 시도하여 가장 짧은 다리를 출력하였다.

구체적인 BFS에서의 조건은 주석을 통해 확인할 수 있다.

혹시 모든 섬이 연결되어있는 경우도 있을 것 같아서 그부분도 고려하였다.

 

코드

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

public class Main {

    static int N;
    static int[][] map;
    static int[] moveX = {0,0,1,-1};
    static int[] moveY = {1,-1,0,0};

    //최소의 다리
    //바다로만 갈 수 있다고 생각하고, BFS로 최단거리를 구해보기?

    static HashMap<Integer,Queue<point>> islandMap = new HashMap<>();


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

        map = new int[N][N];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int coloring = 2;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {

                //색칠해야됨
                if(map[i][j] == 1) {

                    //섬 좌표 따로 저장
                    Queue<point> q = new LinkedList<>();
                    islandMap.put(coloring, q);
                    coloringBFS(j, i, coloring,q);


                    coloring++;
                }

            }
        }
        int answer = 99999999;
        //2 ~ coloring -1 = 섬별 idx
        for(int i=2; i<coloring; i++) {
            int cur = BFS(i, islandMap.get(i));
            //System.out.println(cur);
            answer = Math.min(cur,answer);
        }
        System.out.println(answer);
    }

    //섬 구분
    public static void coloringBFS(int x, int y, int color, Queue<point> island){
        Queue<point> q = new LinkedList<>();
        q.add(new point(x, y));
        //얘도 색칠
        map[y][x] = color;
        int nextX, nextY;
        boolean isoutside = false;

        while(!q.isEmpty()) {
            point cur = q.poll();

            for(int i=0; i<4; i++) {
                nextX = cur.x + moveX[i];
                nextY = cur.y + moveY[i];

                //배열 범위
                if(nextX < 0 || nextX > N-1 || nextY <0 || nextY > N-1) continue;

                //방문 안했고, 육지면 추가
                if(map[nextY][nextX] != color && map[nextY][nextX] != 0) {
                    q.add(new point(nextX, nextY));
                    map[nextY][nextX] = color;
                }
                //바다면 (가장자리 좌표)
                if(map[nextY][nextX] == 0) {
                    isoutside = true;
                }
            }

            if(isoutside) {
                isoutside = false;
                //가장자리섬들만 따로 추가
                island.add(cur);
            }
        }
    }

    //바다 탐색
    public static int BFS(int color, Queue<point> q) {
        int visited[][] = new int[N][N];

        //우리 섬 색
        int size, nextX, nextY;
        int round = 0;

        while(!q.isEmpty()) {
            size = q.size();

            for(int i=0; i<size; i++) {
                point cur = q.poll();
                visited[cur.y][cur.x] = 1; //방문체크

                //새로운 섬이면 종료
                if(map[cur.y][cur.x] != 0 && map[cur.y][cur.x] != color) {
                    return round-1;
                }

                for(int a =0; a<4; a++) {
                    nextX = cur.x + moveX[a];
                    nextY = cur.y + moveY[a];

                    //배열 범위
                    if(nextX < 0 || nextX > N-1 || nextY <0 || nextY > N-1) continue;

                    //방문 안했고, 바다면 추가
                    if(visited[nextY][nextX] == 0 && map[nextY][nextX] != color) {
                        q.add(new point(nextX, nextY));
                        visited[nextY][nextX] = 1;
                    }
                }                
            }
            round++;
        }
        return 99999999;
    }
}

class point{
    int x;
    int y;

    public point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public void print() {
        System.out.println("y: " + y + " x: " + x);
    }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!