[BOJ/Java] 2146. 다리 만들기

[BOJ/Java] 2146. 다리 만들기

2146번: 다리 만들기

---

문제 해석

이 문제에서는 N x N 크기의 지도 위에 여러 섬이 표시되어 있으며, 각 섬은 1로, 바다는 0으로 표시된다. 목표는 서로 다른 두 섬을 연결하는 가장 짧은 다리를 찾는 것이다. 다리는 수평 또는 수직으로만 연결할 수 있으며, 다리의 길이는 바다를 지나는 칸의 수로 결정된다.

풀이 과정

• sol 메소드는 섬의 경계를 설정하고(setBoundary), 섬들 사이의 최단 다리 거리를 찾는(findWay) 두 가지 주요 작업을 수행한다.
• setBoundary에서는 BFS를 사용하여 각 섬의 경계를 찾고, 해당 섬의 모든 지점을 고유 번호로 표시한다.
• findWay에서는 각 섬의 경계 지점에서 시작하여 다른 섬에 도달할 때까지의 최소 거리를 계산한다. 이 과정에서도 BFS를 활용하며, 최소 거리가 현재 저장된 최소 거리보다 클 경우 탐색을 중단한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No2146;

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

public class Main {
    private int[][] graph; // 지도 정보
    private int ans = Integer.MAX_VALUE; // 최소 다리 길이
    private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 4방향 이동
    boolean[][] visited; // 방문 여부
    Queue<Point> queue; // BFS에 사용할 큐

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine()); // 지도 크기
        graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        sol(); // 문제 해결 메소드 호출
        sb.append(ans); // 결과 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        setBoundary(); // 섬의 경계 설정
        findWay(); // 최단 다리 길이 계산
    }

    // 섬의 경계 설정
    private void setBoundary() {
        int idx = 2; // 섬 구분 번호 (1 이상 사용)
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if (graph[i][j] == 1) {
                    findBoundary(i, j, idx++); // 섬마다 고유 번호 부여
                }
            }
        }
    }

    // BFS로 섬의 내부를 탐색하며 경계 설정
    private void findBoundary(int x, int y, int idx) {
        queue = new ArrayDeque<>();
        queue.offer(new Point(x, y));
        graph[x][y] = idx;
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (checkStatus(nx, ny) && graph[nx][ny] == 1) {
                    graph[nx][ny] = idx;
                    queue.offer(new Point(nx, ny));
                }
            }
        }
    }

    // 다른 섬에 도달하기 위해 BFS 실행
    private void findWay() {
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if (graph[i][j] > 1) { // 섬의 경계에서 시작
                    ans = Math.min(ans, getWay(i, j, graph[i][j]));
                }
            }
        }
    }

    // 다리 길이 계산
    private int getWay(int x, int y, int num) {
        visited = new boolean[graph.length][graph.length];
        queue = new ArrayDeque<>();
        queue.offer(new Point(x, y, 0));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point p = queue.poll();

            if (p.cnt >= ans) return Integer.MAX_VALUE; // 최소 거리 초과 시 종료

            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (checkStatus(nx, ny) && !visited[nx][ny]) {
                    if(graph[nx][ny] != num && graph[nx][ny] != 0) { // 다른 섬 도달
                        return p.cnt;
                    }
                    else if(graph[nx][ny] == 0) { // 바다
                        visited[nx][ny] = true;
                        queue.offer(new Point(nx, ny, p.cnt + 1));
                    }
                }
            }
        }

        return Integer.MAX_VALUE;
    }

    class Point {
        int x, y, cnt;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

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

시간 복잡도 분석

이 알고리즘의 시간 복잡도는O(N^2)이다. 각 섬의 경계를 설정하는 데 O(N^2) 시간이 걸리고, 각 섬의 경계에서 다른 섬으로의 최소 거리를 찾는 데에도 최대 O(N^2) 시간이 소요된다.

느낀점

이 문제를 통해 복잡한 그래프 탐색 문제를 해결하는 방법을 배웠다. 각 섬을 구분하고 각 섬의 경계에서 다른 섬까지의 최소 거리를 효과적으로 찾는 것이 중요했다. 이러한 문제 해결 기법은 앞으로 다양한 그래프 탐색 문제에 적용할 수 있을 것이다.