[백준 JAVA] 2146 다리 만들기

2146 다리 만들기

https://www.acmicpc.net/problem/2146

문제설명

그래프를 탐색하여 섬들 간의 최단 다리 길이를 찾는다.

접근방식

O(N^4) 시간복잡도

• DFS 탐색: 섬을 번호 매기기 위해 O(N^2) 시간이 걸린다.
• BFS 탐색: 각 섬에서 다른 섬까지의 최단 거리를 찾기 위해 O(N^4) 시간이 걸린다.
  (각 셀에 대해 BFS를 수행할 수 있기 때문)

즉, 지도 크기 N이 커질수록 처리 시간이 급격히 증가한다.

 

문제 조건 분석 과정

• 모든 섬을 탐색하여 고유 번호를 매기고 (DFS 사용)
• 각 섬에서 다른 섬까지의 최단 거리를 계산 (BFS 사용)
• 섬이 여러 개 있을 수 있으며, 모든 섬에 대해 다리 길이를 계산해야 함

전체코드

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

public class Main {
    static int N;  // 지도 크기
    static int res = 10001;  // 결과를 큰 값으로 초기화
    static int[][] req = new int[101][101];  // 섬 번호를 저장할 지도
    static boolean[][] isIslandCheck = new boolean[101][101];  // 방문 여부를 확인할 지도
    static int[] dx = {1, 0, -1, 0};  // x 방향으로 이동할 때의 변화 (오른쪽, 아래, 왼쪽, 위)
    static int[] dy = {0, 1, 0, -1};  // y 방향으로 이동할 때의 변화 (오른쪽, 아래, 왼쪽, 위)

    // DFS를 이용해 섬을 탐색하고 번호를 매긴다
    static void dfs(int y, int x, int islandNum) {
        isIslandCheck[y][x] = true;  // 현재 셀을 방문 처리
        req[y][x] = islandNum;  // 현재 셀에 섬 번호를 부여

        // 4 방향으로 이동
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];  // 새로운 y 좌표
            int nx = x + dx[i];  // 새로운 x 좌표
            // 경계 확인
            if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

            // 동일 섬의 미방문 셀인 경우 DFS 계속 수행
            if (req[ny][nx] != 0 && !isIslandCheck[ny][nx]) dfs(ny, nx, islandNum);
        }
    }

    // BFS를 이용해 섬을 확장하며 가장 짧은 다리 길이를 찾는다
    static void enlargeIsland(int[][] map, int islandNum) {
        boolean[][] check = new boolean[101][101];  // BFS 중 방문 여부를 확인할 지도
        Queue<Island> queue = new LinkedList<>();  // BFS를 위한 큐

        // 현재 섬의 모든 셀을 큐에 추가
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == islandNum) {
                    queue.add(new Island(i, j, 0));  // 시작 셀과 거리 0을 큐에 추가
                    check[i][j] = true;
                }
            }
        }

        // BFS 수행
        while (!queue.isEmpty()) {
            Island position = queue.poll();  // 현재 위치와 거리 얻기

            // 4 방향으로 이동
            for (int i = 0; i < 4; i++) {
                int ny = position.y + dy[i];  // 새로운 y 좌표
                int nx = position.x + dx[i];  // 새로운 x 좌표
                // 경계 확인
                if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

                // 다른 섬을 발견하면, 현재까지의 거리로 결과 업데이트
                if (map[ny][nx] != islandNum && req[ny][nx] != 0) {
                    if (res > position.cnt && position.cnt != 0) res = position.cnt;
                } else {
                    // 물인 경우와 방문하지 않은 경우
                    if (map[ny][nx] == 0 && !check[ny][nx]) {
                        check[ny][nx] = true;
                        queue.add(new Island(ny, nx, position.cnt + 1));  // 거리 증가시켜 큐에 추가
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // 지도 크기 입력

        // 지도 입력
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                req[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int islandNum = 1;  // 섬 번호 초기화
        // 모든 섬에 번호를 매기기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!isIslandCheck[i][j] && req[i][j] != 0) {
                    dfs(i, j, islandNum);
                    islandNum++;
                }
            }
        }

        // 모든 섬에 대해 가장 짧은 다리 찾기
        for (int i = 1; i < islandNum; i++) {
            int[][] map = req.clone();  // 지도 복사
            enlargeIsland(map, i);
        }
        
        System.out.println(res);
    }
}

// 위치와 거리를 나타내는 클래스
class Island {
    int y;
    int x;
    int cnt;

    Island(int y, int x, int cnt) {
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}