BOJ_2146 : 다리 만들기

👉 문제링크

---

---

🔸 문제 분석 🔸

• N x N 지도에 2개 이상의 섬이 주어진다. 섬은 1로 상하좌우 연결된 덩어리이다.
• 서로 다른 두 섬 사이에 다리 하나를 놓을 때, 다리의 길이의 최소값을 출력한다.

🔸 문제 풀이 🔸

• 단순한 그래프 탐색 문제이다.
• 먼저 지도 상의 같은 섬 소속 1들을 묶어줄 필요가 있다.
  • 다리를 지을 때, 서로 다른 섬인지 알아야 하므로 섬 덩어리 별 다른 값을 넣는다.
  • 단순한 4방 탐색이므로, DFS나 BFS 상관 없이 사용하면 되는데, 여기서는 DFS로 통일해서 사용했다.
• 섬 사이에 다리가 놓이는지 확인해야 한다.
  • DFS로 한쪽 섬의 끝에서 다른 섬을 발견 할 때까지 탐색한다.
  • 한번 다리가 완성되면, 최소값으로 저장하고 백트래킹에 이용한다.

🔸 코드 🔸

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

public class Main {
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    private static int min;
    private static int[][] map;
    private static int[][] visited;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        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 cnt = 0; // 섬의 갯수
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    dfs_island(i, j, ++cnt + 1);
                }
            }
        }

        // 다리 짓기
        min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > 1) {
                    visited = new int[N][N];
                    for (int k = 0; k < N; k++) {
                        for (int l = 0; l < N; l++) {
                            visited[k][l] = Integer.MAX_VALUE;
                        }
                    }
                    dfs_bridge(i, j, map[i][j], 0);
                }
            }
        }

        // Output
        bw.write(Integer.toString(min));
        bw.flush();
    }

    private static void dfs_bridge(int row, int col, int num, int depth) {
        visited[row][col] = depth;

        if (depth >= min)
            return;

        for (int i = 0; i < 4; i++) {
            int r = row + dx[i];
            int c = col + dy[i];
            if (0 <= r && r < map.length && 0 <= c && c < map.length && visited[r][c] > depth + 1 && map[r][c] != num) {
                if (map[r][c] == 0) {
                    dfs_bridge(r, c, num, depth + 1);
                } else {
                    min = Math.min(min, depth);
                    return;
                }
            }
        }
    }

    private static void dfs_island(int row, int col, int iNum) {
        map[row][col] = iNum;

        for (int k = 0; k < dx.length; k++) {
            int r = row + dx[k];
            int c = col + dy[k];
            if (0 <= r && r < map.length && 0 <= c && c < map.length && map[r][c] == 1) {
                dfs_island(r, c, iNum);
            }
        }
    }
}

🔸 코드 해석 🔸

• dfs_island() 메서드를 이용해 dfs로 인접한 1들을 묶어 섬 덩어리를 표시했다.
• dfs_bridge() 메서드에서 dfs 방식으로 다리를 그려가며 최소값을 찾았다.
  • 최소값을 min에 저장하고 해당 길이는 더 보지 않아도 되므로, 즉시 return한다.
  • 최소값을 찾은 후에는 해당 값으로 백트래킹을 수행했다.

---

🔸 end 🔸

• 경계값(minimum)에서 2회 틀렸다.
  • N이 100이하의 자연수지만, 항상 섬이 2개이상 존재한다고 했으므로 N의 최소값은 2이다.
  • dfs_island() 메서드에서 map[row][col] = iNum 으로 값을 넣는 부분을 4방탐색 if문 안에 넣는 방식으로 구현했다가 N이 2일때 틀리게 되었다.
  • 시작 위치만 값이 씌이지 않았던 것이다.
• 알고리즘 자체는 단순한 그래프 탐색이었는데, 문제 태그에는 BFS만 적혀있어서 놀랐다. 확실히 다리를 짓는건 최단거리를 찾는 것이기 때문에 BFS를 사용했어야 했지만, 문제 조건이 까다롭지 않아서 DFS + 백트래킹으로 풀이가 된 것 같다.
• 테스트 케이스를 정리했다.