[Bakejoon] 미로만들기

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

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

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

    private static int n;
    private static int answer;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        init();

        sol();

        print();
    }

    private static void sol() {
        bfs_0_1();
    }

    private static void bfs_0_1() {
        Deque<int[]> dq = new ArrayDeque<>();
        int[][] dist = new int[n][n];
        boolean[][] visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        dq.offer(new int[] { 0, 0 });
        dist[0][0] = 0;
        visited[0][0] = true;

        while (!dq.isEmpty()) {
            int[] arr = dq.poll();
            int y = arr[0];
            int x = arr[1];

            for (int i = 0; i < 4; i++) {
                int py = y + dy[i];
                int px = x + dx[i];

                if (isOutOfRange(py, px) || visited[py][px]) {
                    continue;
                }

                if (dist[py][px] >= dist[y][x] + map[py][px]) {
                    dist[py][px] = dist[y][x] + map[py][px];
                    if (map[py][px] == 1) {
                        dq.addLast(new int[] { py, px });
                    } else {
                        dq.addFirst(new int[] { py, px });
                    }
                    visited[py][px] = true;
                }
            }
        }

        answer = dist[n - 1][n - 1];
    }

    private static boolean isOutOfRange(int y, int x) {
        return y < 0 || x < 0 || y >= n || x >= n;
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split("");

            for (int j = 0; j < n; j++) {
                // 실제 입력값말고 해당 칸으로 이동하는 가중치로 변환한다.
                map[i][j] = Integer.parseInt(s[j]) == 1 ? 0 : 1;
            }
        }
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• 0-1 BFS

풀이 방법

• 우선 0-1 BFS를 처음 들어봤다.

• Dijkstra가중치가 0또는 1일 경우 사용할 수 있는 최적화 알고리즘이다.

• Deque를 사용하여 각 칸으로 이동하는 가중치가 0인경우 addFirst, 가중치가 1인겨우 addLast를 해준다.

• 이를 통해 기존 Dijkstra 에서 PriorityQueue를 사용하여 O(E logV) 인 반면 0-1 BFS 경우 O(V + E)로 더 효율적으로 해결할 수 있다.