백준 1584 (게임) - java

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

 

문제

세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)

세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.

세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오.

 

유형 : 다익스트라

 

접근 방식

• 500 * 500 좌표계이다.
• 주어지는 영역의 개수가 최대 100개이므로 100 * 2500 순회이기 때문에 각 구역을 1,2로 구분하여 순회한다.
• dis[500][500]의 값을 기준으로 최솟값을 출력한다.

 

전체 코드

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

public class BOJ_1584_게임 {

    static int n,m;

    static int[][] board = new int[501][501];

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());

        for(int a = 1 ; a <= n ; a++) {
            st = new StringTokenizer(br.readLine()," ");

            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            for(int i = Math.min(x1,x2) ; i <= Math.max(x1,x2) ; i++) {
                for(int j = Math.min(y1,y2) ; j <= Math.max(y1,y2) ; j++) {
                    board[i][j] = 1;
                }
            }
        }

        st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());

        for(int a = 1 ; a <= m ; a++) {
            st = new StringTokenizer(br.readLine()," ");

            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            for(int i = Math.min(x1,x2) ; i <= Math.max(x1,x2) ; i++) {
                for(int j = Math.min(y1,y2) ; j <= Math.max(y1,y2) ; j++) {
                    board[i][j] = 2;
                }
            }
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (x,y) -> x[2] - y[2]
        );

        int[][] dis = new int[501][501];

        for(int i = 0 ; i <= 500 ; i++) {
            for(int j = 0 ; j <= 500 ; j++) {
                dis[i][j] = Integer.MAX_VALUE;
            }
        }

        dis[0][0] = 0;
        pq.add(new int[]{0,0,0});

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();

            if(dis[cur[0]][cur[1]] < cur[2])
                continue;

            for(int i = 0 ; i < 4 ; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

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

                if(board[nx][ny] == 2)
                    continue;

                if(dis[nx][ny] > cur[2] + board[nx][ny]) {
                    dis[nx][ny] = cur[2] + board[nx][ny];
                    pq.add(new int[]{nx,ny,dis[nx][ny]});
                }
            }
        }

        System.out.println(dis[500][500] == Integer.MAX_VALUE ? -1 : dis[500][500]);

        br.close();
    }
}