백준 14497 - 주난의 난

문제

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

리뷰

다익스트라 또는 0-1 BFS로 풀이할 수 있는 문제였다.

다익스트라의 경우 dist 를 $N \times M$ 2차원 배열의 형태로 정의한뒤 시작점을 0,
도착점을 1로 비용 설정해주어 map의 값에 따라 다익스트라 로직을 진행해주면
도착점까지의 최소 비용을 dist 값을 통해 구할 수 있다.

0-1 BFS의 경우 덱을 이용하여 비용이 없는(0) 경로가 우선시 되어 탐색될 수 있도록
offerFirst 해주며 도착점에 도달하였을 시 비용을 반환해주는 방식으로 구성하였다.

시간복잡도
다익스트라 로직의 시간복잡도는 $O(ElogV)$ 로 수렴하는데 $E=4 \times N \times M$, $V=N \times M$
이고 0-1 BFS 로직의 경우 $O(N \times M)$의 복잡도를 띈다.

두 로직 모두 $N=M=500$인 최악의 경우에도 무난히 2초의 제한 조건을 통과한다.

코드

다익스트라

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    static int N, M;
    static int[][] map;
    static int[][] dist;

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

        int sx, sy, ex, ey;
        st = new StringTokenizer(br.readLine());
        sy = parseInt(st.nextToken()) - 1;
        sx = parseInt(st.nextToken()) - 1;
        ey = parseInt(st.nextToken()) - 1;
        ex = parseInt(st.nextToken()) - 1;

        String line;
        char val;
        for (int y = 0; y < N; y++) {
            line = br.readLine();
            for (int x = 0; x < M; x++) {
                val = line.charAt(x);

                if (val == '1' || val == '0') {
                    map[y][x] = val - '0';
                    continue;
                }

                map[y][x] = 0;
            }
        }
        map[ey][ex] = 1;

        dijkstra(sx, sy);
        System.out.println(dist[ey][ex]);
        br.close();
    }


    static void dijkstra(int sx, int sy) {
        for (int[] ints : dist) {
            Arrays.fill(ints, MAX_VALUE);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.w));
        dist[sy][sx] = 0;
        pq.offer(new Node(sx, sy, dist[sy][sx]));

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        int nx, ny;
        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (dist[cur.y][cur.x] < cur.w)
                continue;

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

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

                if (dist[ny][nx] > dist[cur.y][cur.x] + map[ny][nx]) {
                    dist[ny][nx] = dist[cur.y][cur.x] + map[ny][nx];
                    pq.offer(new Node(nx, ny, dist[ny][nx]));
                }
            }
        }
    }

    static class Node {
        int x, y, w;

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

0-1 BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;

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

        st = new StringTokenizer(br.readLine());
        int sy = parseInt(st.nextToken()) - 1;
        int sx = parseInt(st.nextToken()) - 1;
        int ey = parseInt(st.nextToken()) - 1;
        int ex = parseInt(st.nextToken()) - 1;

        String line;
        char val;
        for (int y = 0; y < N; y++) {
            line = br.readLine();
            for (int x = 0; x < M; x++) {
                val = line.charAt(x);
                if (val == '#' || val == '*')
                    continue;

                map[y][x] = val - '0';
            }
        }

        map[ey][ex] = 1;
        System.out.println(bfs(sx, sy, ex, ey));
        br.close();
    }

    static int bfs(int sx, int sy, int ex, int ey) {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(sx, sy, 0));
        visited[sy][sx] = true;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int nx, ny;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.x == ex && cur.y == ey) return cur.level;

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

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

                if (visited[ny][nx]) continue;

                visited[ny][nx] = true;
                if (map[ny][nx] == 0) {
                    queue.offerFirst(new Node(nx, ny, cur.level));
                } else {
                    queue.offerLast(new Node(nx, ny, cur.level + 1));
                }
            }
        }

        return -1;
    }

    static class Node {
        int x, y, level;

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

결과

다익스트라가 0-1 BFS보다 근소하게 빠른 것으로 확인되었다.