백준 2146 - 다리 만들기

문제

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

리뷰

BFS를 응용하여 풀이할 수 있는 문제였다. 로직의 전개는 다음 순서로 이뤄진다.

• 바다를 -1, 땅을 0으로 초기화하여 저장한다.

• 각 좌표를 검사하여 0인 경우 paintBfs 함수를 통해 땅 영역에 번호를 표기한다.
  이 로직에서는 동시에 땅 영역에서 가장자리에 해당하는 좌표들을 start에
  저장한다.

• start에 저장해논 각 땅 영역의 가장자리들에서 다른 땅 영역까지의 거리를
  bfs를 돌리며 minDist에 갱신하여 최단 거리를 도출한다.

로직의 시간복잡도는 복잡도가 가장 큰 이중 for문을 돌며 paintBfs를 실행하는
부분에서 $O(N^4)$으로 수렴하며, 최악의 경우 $N=100$일 때 1억번의 연산을
수행한다. 따라서 제한 조건인 2초를 무난히 통과할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int minDist = MAX_VALUE;
    static List<Node> start=new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = parseInt(br.readLine());
        map = new int[N][N];

        StringTokenizer st;
        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++)
                map[y][x] = parseInt(st.nextToken()) - 1;
        }

        int k = 1;


        for (int y = 0; y < N; y++)
            for (int x = 0; x < N; x++) { // O(N^4)
                if (map[y][x] == 0) {
                    paintBfs(x, y, k++); // O(N^2)
                }
            }

        for (Node node : start) {
            bfs(node.x, node.y);
        }

        System.out.print(minDist);
        br.close();
    }

    static void bfs(int x, int y) { // O(N^2)
        visited = new boolean[N][N];

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(x, y, 0));
        int value = map[y][x];
        visited[y][x] = true;

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int cx = current.x;
            int cy = current.y;

            if (map[cy][cx] != -1 && map[cy][cx] != value) {
                minDist = Math.min(minDist, current.level);
                continue;
            }

            for (int i = 0; i < dx.length; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;

                if (!visited[ny][nx]) {
                    visited[ny][nx] = true;

                    if (map[ny][nx] == -1) {
                        queue.offer(new Node(nx, ny, current.level + 1));
                        continue;
                    }

                    queue.offer(new Node(nx, ny, current.level));
                }
            }

        }
    }

    static void paintBfs(int x, int y, int value) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(x, y, 0));
        map[y][x] = value;

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if(isEdge(current))
                start.add(new Node(current.x, current.y, 0));

            for (int i = 0; i < dx.length; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;

                if (map[ny][nx] == 0) {
                    map[ny][nx] = value;
                    queue.offer(new Node(nx, ny, 0));
                }
            }
        }
    }

    static boolean isEdge(Node current){
        for(int i=0; i<dx.length; i++){
            int nx=current.x+dx[i];
            int ny=current.y+dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;

            if(map[ny][nx]==-1)
                return true;
        }

        return false;
    }

    static class Node {
        int x, y, level;

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

결과