[Boj_1584] 게임

📎 문제 링크

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

 

▸ 문제

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

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

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

 

 

▸ 입력

첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 반대 모서리이다. 그 다음 줄에는 죽음의 구역의 수 M이 주어진다. 다음 줄부터 M개의 줄에는 죽음의 구역의 정보가 위험한 구역의 정보와 같이 주어진다. 주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는, 더 심한 구역이 해당된다. 예를 들어, 죽음+위험 = 죽음, 위험+안전 = 위험, 위험+위험 = 위험, 죽음+안전 = 죽음이다. 위험한 구역이 아무리 겹쳐도 생명은 1씩 감소된다. 생명의 감소는 구역에 들어갈 때만, 영향을 미친다. 예를 들어, (500, 500)이 위험한 구역일 때는, (500, 500)에 들어갈 때, 생명이 1 감소되지만, (0, 0)이 위험한 구역이더라도 생명은 감소되지 않는다. 마찬가지로, (0, 0)이 죽음의 구역이더라도 세준이는 이미 그 곳에 있으므로 세준이에게 영향을 미치지 않는다. N과 M은 50보다 작거나 같은 자연수이다.

 

▸ 출력

첫째 줄에 정답을 출력한다. 만약 (500, 500)으로 갈 수 없을 때는 -1을 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 5
• 🔔  문제 유형 : 그래프 이론, 그래프 탐색, 최단 경로, 데이크스트라, 0-1 너비 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

다익스트라 알고리즘을 사용해서 풀 수 있는 문제였다.

 

전체 맵의 크기가 500x500이고, N+M의 최대치는 100이므로 O(100*500*500) = O(25,000,000)이기 때문에

위험 구역, 죽음 구역에 대한 정보를 직접 맵에 기록했다.

 

죽음 구역, 위험 구역, 안전 구역이 모두 정해졌으니,

다익스트라 또는 0-1 너비 우선 탐색을 진행하여 문제를 해결할 수 있다.

 

나의 경우는  0-1 너비 우선 탐색을 진행하여 문제를 해결했다.

 

위 풀이대로 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 23900KB
시간 : 276ms

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

public class Main {
    static final int INF = 987654321;
    static final int WARNING = 1;
    static final int DEATH = 2;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static PriorityQueue<Pos> pq;
    static public class Pos implements Comparable<Pos> {
        int x; int y;
        int dist;
        public Pos (int x, int y, int dist) {
            this.x = x; this.y = y;
            this.dist = dist;
        }
        @Override
        public int compareTo(Pos o) {
            return this.dist - o.dist;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[501][501];
        int n = Integer.parseInt(br.readLine()); // 위험한 구역의 수
        StringTokenizer st;
        // 위험한 구역의 정보
        int x1, y1, x2, y2;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            // 구역 표시
            marking(x1, y1, x2, y2, WARNING);
        }

        int m = Integer.parseInt(br.readLine()); // 죽음의 구역의 수
        // 죽음의 구역의 정보
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            marking(x1, y1, x2, y2, DEATH);
        }

        int ans = bfs();

        System.out.println(ans);
    }

    private static void marking(int x1, int y1, int x2, int y2, int mark) {
        // (x1, y1) 구역의 모서리, (x2, y2) 구역의 반대 모서리
        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++) {
                map[i][j] = mark;
            }
        }
    }

    private static int bfs() {
        int[][] dist = new int[501][501];
        for (int[] row : dist) Arrays.fill(row, INF);

        pq = new PriorityQueue<>();
        pq.offer(new Pos(0, 0, 0));
        dist[0][0] = 0;

        while (!pq.isEmpty()) {
            Pos now = pq.poll();
            int nowDist = now.dist;

            for (int d = 0; d < 4; d++) {
                int nx = dx[d] + now.x;
                int ny = dy[d] + now.y;

                // 범위 체크, 죽음의 구역 X
                if (rangeCheck(nx, ny) || map[nx][ny] == DEATH) continue;

                if (dist[nx][ny] <= nowDist + map[nx][ny]) continue;

                dist[nx][ny] = nowDist + map[nx][ny];
                
                if (map[nx][ny] == 0) pq.offer(new Pos(nx, ny, nowDist)); // 안전한 구역
                else pq.offer(new Pos(nx, ny, nowDist+1)); // 위험한 구역
            }
        }

        return dist[500][500] == INF ? -1 : dist[500][500];
    }

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

 

해결 완료 ! 🔥