[백준/JAVA] BOJ 1584 - 게임

0-1 너비 우선 탐색에 대해 아십니까

👀 문제

1584번: 게임 ✨ 골드 5

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

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

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

예제 입력

1
500 0 0 500
1
0 0 0 0

예제 출력

1000

🔑 키포인트

0-1 너비 우선 탐색 최단 경로

✍️ 코드

📍 0-1 너비 우선 탐색을 사용하면 쉽게 풀 수 있는 문제

🤔 안전한 구역은 0, 위험한 구역은 1, 죽음의 구역은 2로 구분

💡 위험한 구역이라면 now.level + 1 해서 offerLast 안전한 구역이라면 now.level 그대로 offerFirst 해 준다

😅 코드가 길고 뭔가 더러워 보여서 맘에 안 든다... 쩝

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

public class BOJ1584_게임 {
    static class Node {
        int x, y, level;

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

    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static int[][] map;
    static boolean[][] visited;
    static ArrayDeque<Node> dq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        map = new int[501][501];
        visited = new boolean[501][501];

        int n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            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());

            int xLen = Math.abs(x1 - x2);
            int yLen = Math.abs(y1 - y2);

            int startX = Math.min(x1, x2);
            int startY = Math.min(y1, y2);

            xLen = startX + xLen + 1;
            yLen = startY + yLen + 1;

            for (int xx = startX; xx < xLen; xx++) {
                for (int yy = startY; yy < yLen; yy++) {
                    map[xx][yy] = 1; // 위험한 구역
                }
            }
        }
        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            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());

            int xLen = Math.abs(x1 - x2);
            int yLen = Math.abs(y1 - y2);

            int startX = Math.min(x1, x2);
            int startY = Math.min(y1, y2);

            xLen = startX + xLen + 1;
            yLen = startY + yLen + 1;

            for (int xx = startX; xx < xLen; xx++) {
                for (int yy = startY; yy < yLen; yy++) {
                    map[xx][yy] = 2; // 죽음의 구역 (들어갈 수 없음)
                }
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        dq = new ArrayDeque<>();
        dq.offer(new Node(0, 0, 0));
        visited[0][0] = true;

        while (!dq.isEmpty()) {
            Node now = dq.poll();
            if (now.x == 500 && now.y == 500) {
                return now.level;
            }
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

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

        return -1;
    }

    static boolean isValid(int x, int y) {
        if (x < 0 || x > 500 || y < 0 || y > 500) {
            return false;
        } else if (visited[x][y]) {
            return false;
        } else if (map[x][y] == 2) {
            return false;
        }
        return true;
    }
}