백준 1584 - 게임

문제

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

리뷰

다익스트라로 풀이할 수 있는 간단한 문제였다.

우선 안전/위험/죽음의 지역을 구분하기 위해 map이라는 2차원 배열을
정의해주었다. 또한, 다익스트라 로직을 구성하기 위한 dist 2차원 배열도
정의했다.

setArea 함수는 모서리 좌표들을 받아서 해당 지역을 표시해주는 메서드로,
이 메서드를 활용하여 위험한 지역과 죽음의 지역을 입력을 받으며 표시해주었다.
이후 다익스트라를 돌리며, dist[500][500]까지 도달하는데 필요한 최소 비용을
도출해주면 된다.

로직의 시간복잡도는 다익스트라의 $O(ElogV)$로 수렴하고, 이는 $V=500$,
$E=4\times 500^2$이므로 무난히 제한 조건 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[][] map = new int[501][501];
    static int[][] dist = new int[501][501];

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

        StringTokenizer st;

        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            x1 = parseInt(st.nextToken());
            y1 = parseInt(st.nextToken());
            x2 = parseInt(st.nextToken());
            y2 = parseInt(st.nextToken());

            setArea(x1, y1, x2, y2, 1);
        }

        int M = parseInt(br.readLine());

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            x1 = parseInt(st.nextToken());
            y1 = parseInt(st.nextToken());
            x2 = parseInt(st.nextToken());
            y2 = parseInt(st.nextToken());

            setArea(x1, y1, x2, y2, 2);
        }

        initDist();
        dijkstra();

        System.out.println(dist[500][500] == MAX_VALUE ? -1 : dist[500][500]);
        br.close();
    }

    static void initDist() {
        for (int[] line : dist) {
            Arrays.fill(line, MAX_VALUE);
        }
    }

    static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.w));
        pq.offer(new Node(0, 0, 0));
        dist[0][0] = 0;

        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 = dx[i] + cur.x;
                ny = dy[i] + cur.y;

                if (nx < 0 || nx > 500 || ny < 0 || ny > 500)
                    continue;

                if (map[ny][nx] == 2) 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 void setArea(int x1, int y1, int x2, int y2, int val) {
        int startX = Math.min(x1, x2);
        int startY = Math.min(y1, y2);
        int endX = Math.max(x1, x2);
        int endY = Math.max(y1, y2);

        for (int x = startX; x <= endX; x++)
            for (int y = startY; y <= endY; y++)
                map[y][x] = val;
    }

    static class Node {
        int x, y, w;

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

결과