[JAVA] 백준 2146번: 다리 만들기

요구 사항

두개의 섬을 이을 수 있는 가장 짧은 다리의 길이를 구하라

 

문제 해결

 

1.  섬과 바다를 구분하는 어레이를 만든다.

2. 각각의 섬을 구분할 수 있는 어레이를 만든다.

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

  3-2 각각의 섬 가장 자리로 부터 떨어진 거리의 값을 구하는 어레이에서, 새로운 좌표가 바다인데 이미 값이 들어있는 경우에는 현재 값과 해당 좌표의 값을 더한 후 어레이 리스트에 저장

  3-3 가장 자리로부터 떨어진 값을 구하는 어레이에서 다음 좌표가 원 출발지와 다른 땅일 경우 현재 값을 결과 어레이 리스트에 저장

4. 어레이 리스트에서 가장 작은 값을 구한다.

 

---

1. 섬과 바다를 구분하는 어레이를 만든다.

input 값을 모두 받아 어레이에 저장해보자 (info에 저장)

for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = true;
                info[i][j] = sc.nextInt();
            }
        }

 

---

2. 각각의 섬을 구분할 수 있는 어레이를 만든다.

color 어레이에 각각의 섬에 알맞는 인덱스 번호를 할당해 주었다.

각각의 섬은 구분하는 방법은 dfs를 이용하여 구분하였다.

for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] && info[i][j] == 1) {
                    dfs(i, j, cnt);
                    cnt++;
                }
            }
        }

 

3.  2개의 섬을 최단 거리로 이을 수 있는 방법을 구하자

결과 값을 구하기 위한 로직이다.

간척 사업을 한다고 생각해보자. 땅에서 가장 가까운 거리부터 간척사업을 진행할 것이다. 

제일 먼저 가장자리에서 1만큼 거리가 떨어진 부분 부터 간척사업을 진행 할 것이다. 그리고 이 간척사업은 어떤 땅에서 부터 진행하였는지를 명시해 주면서 큐에 집어 넣었다.

for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] == false) {
                    for (int j2 = 0; j2 < 4; j2++) {
                        int newI = i + aryH[j2];
                        int newJ = j + aryW[j2];
                        if (newI >= 0 && newJ >= 0 && newI < n && newJ < n && visit[newI][newJ]) {
                            dist[newI][newJ] =1;    
                            color[newI][newJ] = color[i][j];                        
                            q.add(new int[] { newI, newJ, color[i][j] });
                            
                        }
                    }
                }
            }
        }

자 이제 큐에는 가장자리에서 1만큼 거리에 떨어져 있는 좌표 값과, 어떤 땅에서 간척사업이 진행되었는지 정보가 저장되어있다.

그럼 이제 큐에서 좌표를 하나씩 꺼내고, 상, 하, 좌, 우 거리 1만큼 떨어진 바다를 대상으로 간척사업을 계속해서 진행해보자.

간척 대상 좌표는 계속해서 큐에 들어갈 것이다.

for (int i = 0; i < 4; i++) {
                int newH = h + aryH[i];
                int newW = w + aryW[i];
                if (newH >= 0 && newW >= 0 && newH < n && newW < n && info[newH][newW] == 0 && dist[newH][newW] == 0) {
                    // 간척 사업을 진행해야 하는 경우 (바다이고, 간척이 진행되지 않았을 경우)
                    dist[newH][newW] = dist[h][w] + 1; // 새롭게 간척하는 땅의 거리를 지정해주고 (기존 땅 + 1)
                    color[newH][newW] = c; // 새롭게 간척하는 땅은 어떤 땅과 연결되어있는 건지 지정해준다.                    
                    q.add(new int[] { newH, newW, color[newH][newW] });                    
                    // System.out.println(newH+","+newW);

간척 사업을 진행하다 보니 어느 덧 다른 땅에 도착하였다. 땅의 좌표 (newH, newW) 가 이전 간척지 좌표가 (h, w) 다리의 길이 중 하나이다. 이 값은 어레이 리스트에 저장해 놓자.

} else if (newH >= 0 && newW >= 0 && newH < n && newW < n 
                        && info[newH][newW] == 1 && c != color[newH][newW]) {
                    // 색상이 다른 땅에 도착했을 때                                        
                    distAry.add(dist[h][w]);

간척 사업을 진행하다 보니 이번에는 다른 땅에서 시작된 간척지에 도착해버렸다. 이때는 이전 간척지 좌표 (h, w)의 값과 다른 간척지 땅의 좌표 (newH, newW) 값의 합이 다리의 길이 중 하나가 된다. 이것도 어레이 리스트에 저장해 놓자.

else if (newH >= 0 && newW >= 0 && newH < n && newW < n && info[newH][newW] == 0
                && dist[newH][newW] != 0 && c != color[newH][newW]){
                    // 색상이 다른 간척된 땅에 도착했을 때
                    distAry.add(dist[h][w]+dist[newH][newW]);                  
                }

어레이 리스트에는 무수히 많은 다리의 길이가 저장되어 있다.

이중 우리는 가장 짧은 다리의 길이가 필요하다.

가장 짧은 다리의 길이를 구해보자

int res = distAry.get(0);
        for (int i = 1; i < distAry.size(); i++) {
            if (res > distAry.get(i)) {
                res = distAry.get(i);
            }
        }
        System.out.println(res);

 

전체 코드이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class baekjoon2146 {
    static boolean[][] visit;
    static int[][] info;
    static int[] aryH = { 0, 0, -1, 1 };
    static int[] aryW = { -1, 1, 0, 0 };
    static int n;
    static int[][] color;
    static int[][] dist;

    public static void main(String[] args) {        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        visit = new boolean[n][n];
        info = new int[n][n];
        color = new int[n][n];
        dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = true;
                info[i][j] = sc.nextInt();
            }
        }
        int cnt = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] && info[i][j] == 1) {
                    dfs(i, j, cnt);
                    cnt++;
                }
            }
        }

        Queue<int[]> q = new LinkedList<>();        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] == false) {
                    for (int j2 = 0; j2 < 4; j2++) {
                        int newI = i + aryH[j2];
                        int newJ = j + aryW[j2];
                        if (newI >= 0 && newJ >= 0 && newI < n && newJ < n && visit[newI][newJ]) {
                            dist[newI][newJ] =1;    
                            color[newI][newJ] = color[i][j];                        
                            q.add(new int[] { newI, newJ, color[i][j] });
                            
                        }
                    }
                }
            }
        }

        ArrayList<Integer> distAry = new ArrayList<>();
        boolean isRun = true;        
        while (!q.isEmpty()) {
            if (isRun == false) {
                break;
            }
            
            int[] location = q.remove();
            int h = location[0];
            int w = location[1];
            int c = location[2];                        

            for (int i = 0; i < 4; i++) {
                int newH = h + aryH[i];
                int newW = w + aryW[i];
                if (newH >= 0 && newW >= 0 && newH < n && newW < n && info[newH][newW] == 0 && dist[newH][newW] == 0) {
                    // 간척 사업을 진행해야 하는 경우 (바다이고, 간척이 진행되지 않았을 경우)
                    dist[newH][newW] = dist[h][w] + 1; // 새롭게 간척하는 땅의 거리를 지정해주고 (기존 땅 + 1)
                    color[newH][newW] = c; // 새롭게 간척하는 땅은 어떤 땅과 연결되어있는 건지 지정해준다.                    
                    q.add(new int[] { newH, newW, color[newH][newW] });                    
                    // System.out.println(newH+","+newW);
                } else if (newH >= 0 && newW >= 0 && newH < n && newW < n 
                        && info[newH][newW] == 1 && c != color[newH][newW]) {
                    // 색상이 다른 땅에 도착했을 때                                        
                    distAry.add(dist[h][w]);                                   
                } else if (newH >= 0 && newW >= 0 && newH < n && newW < n && info[newH][newW] == 0
                && dist[newH][newW] != 0 && c != color[newH][newW]){
                    // 색상이 다른 간척된 땅에 도착했을 때
                    distAry.add(dist[h][w]+dist[newH][newW]);                  
                }                
            }            
        }        
        int res = distAry.get(0);
        for (int i = 1; i < distAry.size(); i++) {
            if (res > distAry.get(i)) {
                res = distAry.get(i);
            }
        }
        System.out.println(res);
    }

    static void dfs(int h, int w, int c) {
        visit[h][w] = false;
        color[h][w] = c;
        for (int i = 0; i < 4; i++) {
            int newH = h + aryH[i];
            int newW = w + aryW[i];
            if (newH >= 0 && newW >= 0 && newH < n && newW < n && visit[newH][newW] && info[newH][newW] == 1) {

                dfs(newH, newW, c);

            }
        }
    }
}

 

로직이 복잡하지도 않고, 어려운 문제도 아니었으나 생각보다 쉽게 구현하지 못하였다.

하다보면 어느덧 익숙해 질 것이다. 

천천히 꾸준히 계속해서 문제를 풀어보자.