[JAVA] boj 2146 다리 만들기

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

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1

3

문제 풀이

보다 쉽게 풀 수 있을 것 같은 문제이지만 코드를 짜다보니 매우 복잡해졌다.

BFS와 약간의 탐욕(?) 알고리즘을 사용하여 문제를 해결하였다.

 

우선은 입력된 map 배열에서 각각의 섬을 찾았다. 2차원 배열은 순회하면서 1로 표시된 곳 중 한번도 방문하지 않은 지점에서 시작하여 BFS를 돌면서 그 지점과 연결된 모든 섬의 영역을 boolean 2차원 배열에 true로 표시하고 리턴해주었다.

 

true로 표시된 영역에서 다른 섬까지 다리를 놓아 가장 짧은 다리의 개수를 찾아야 하기 때문에 boolean 2차원 배열을 순회하면서 true값을 찾았다. 하지만 그 지점이 true라고 해서 반드시 다리를 놓을 수 있는 것은 아니다. 그 지점을 둘러싸고 있는 영역 중 바다가 존재해야만 다리를 놓을 수 있기 때문에 바다가 존재하는지 확인해 주었다.

 

바다가 존재한다면 이 지점 부터 다시 BFS를 돌면서 현재 섬 자기자신이 아닌 map에 1로 표시된 곳을 찾아가는 방법으로 문제를 풀었다.

 

다 풀고나서 생각하니 예시에서 각 섬을 1, 2, 3 으로 표기한다면 1에서 2로 다리를 놓는 경우와 2에서 1로 다리를 놓는 경우는 같은 경우인데 중복해서 체크를 해주고 있다. 이 부분을 개선한다면 실행시간을 더욱 줄일 수 있을 것 같다.

코드

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

public class Main_BJ_2146_다리만들기 {
  static int N, ans;
  static int [][] map;
  static int [][] D = {{-1, 0},{1, 0},{0, -1},{0, 1}};
  static boolean [][] visited;
  
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    N = Integer.parseInt(br.readLine());
    
    map = new int [N][N];
    visited = new boolean[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());
      }
    }
    
    ans = Integer.MAX_VALUE;
            
    bfs();
    
    System.out.println(ans-1);
  }
  
  static boolean [][] splitIsland(int x, int y) {
    Queue<int []> queue = new LinkedList<int[]>();
    queue.offer(new int [] {x, y});
    
    boolean [][] temp = new boolean[N][N];
    
    while(!queue.isEmpty()) {
      int [] now = queue.poll();
      
      if (visited[now[0]][now[1]] || map[now[0]][now[1]] == 0) continue;
      temp[now[0]][now[1]] = true;
      visited[now[0]][now[1]] = true;
      
      for (int i = 0 ; i < 4 ; i++) {
        int nx = now[0] + D[i][0];
        int ny = now[1] + D[i][1];
        
        if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] == 0) continue;
        
        queue.offer(new int [] {nx, ny});
      }
    }
    
    return temp;
  }

  
  static void bfs() {
    for (int i = 0 ; i < N ; i++) {
      for (int j = 0 ; j < N ; j++) {
        if (map[i][j] == 0 || visited[i][j]) continue;
        
        boolean [][] temp = splitIsland(i, j);
        
        for (int n = 0  ; n < N ; n++) {
          for (int m = 0 ; m < N ; m++) {
            // 현재 섬이 아니면 패
            if (!temp[n][m]) continue;
            
            // 4면 중 한 군데라도 바다가 존재하는지 확인
            boolean flag = false;
            
            for (int d = 0 ; d < 4 ; d++) {
              int nx = n + D[d][0];
              int ny = m + D[d][1];
              
              if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
              
              if (map[nx][ny] == 0) {
                flag = true;
                break;
              }
            }
            if (!flag) continue;
            Queue<int []> queue = new LinkedList<>();
            queue.offer(new int [] {n, m, 0});
            
            boolean [][] check = new boolean [N][N];
            
            while(!queue.isEmpty()) {
              int [] now = queue.poll();
              
              // 만약 방문한 적이 있거나 현재 가장 짧은 다리 개수보다 많으면 패스
              if (check[now[0]][now[1]] || ans <= now[2]) continue;
              check[now[0]][now[1]] = true;
              
              // 현재 섬 자기자신이 아니면서 map이 1이면 다른 섬에 도착한 것이므로 다리의 개수를 ans로 갱신
              if (map[now[0]][now[1]] == 1 && !temp[now[0]][now[1]]) {
                ans = Math.min(ans, now[2]);
                continue;
              }
              
              for (int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + D[d][0];
                int ny = now[1] + D[d][1];
                
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                
                queue.offer(new int[] {nx, ny, now[2]+1});
              }
            }
          }
        }
      }
    }
  }
}