[BOJ - JAVA] 17836 - 공주님을 구해라(BFS, DP)

# 주소

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

17836번: 공주님을 구해라!

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Point{
    int x;
    int y;
    int gram;
    int sum;
    Point(int x, int y, int gram,int sum){
        this.x = x;
        this.y = y;
        this.gram = gram;
        this.sum = sum;
    }
}
class Main{
    static int n,m,t;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static boolean[][][] visit;
    static int[][] arr;
    static int MAX = Integer.MAX_VALUE;
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        t = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m][2];
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        bfs();
        if(MAX == Integer.MAX_VALUE || MAX > t)
            System.out.println("Fail");
        else
            System.out.println(MAX);
    }
    static void bfs(){
        queue.offer(new Point(0,0,0,0));
        visit[0][0][0] = true;
        while(!queue.isEmpty()){
            Point now = queue.poll();
            if(arr[now.x][now.y] == 2)
                now.gram = 1;
            if(now.x == n - 1 && now.y == m - 1) {
                MAX = Math.min(now.sum, MAX);
                break;
            }
            int nx, ny;
            for(int i = 0; i < 4; i++){
                nx = now.x + dx[i];
                ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(visit[nx][ny][now.gram])
                    continue;
                if(now.gram == 0){
                    if(arr[nx][ny] == 1)
                        continue;
                }
                queue.offer(new Point(nx,ny,now.gram,now.sum + 1));
                visit[nx][ny][now.gram] = true;
            }
        }
    }
}

처음엔 isOk라는 boolean 타입의 변수로 검을 주었을 때와 아닐 때의 탐색방법을 바꾸려 했습니다.

하지만 이렇게 되면 문제가, bfs 특성상 이미 지나간 길은 더 이상 지나가지 않도록 처리하게 되는데, 그렇게 하면

검을 줍지 않은 채 다른 놈이 길을 이미 지나가버려서, 뒤늦게 검을 주은 놈이 못지나가는 경우가 있을 수 있습니다.

그럴 경우 최단시간이 늘어나 정답이 아니게 됩니다.

이에 따라 반드시 visit배열을 3차원으로 선언하여 사용해야 하는 것입니다.

어떤 조건이 주어져 있을 때 조건에 따라 벽을 부수거나 하는 등의 문제는 2차원 배열에서 1차원을 더해주어서 문제를 푸는 것이 좋겠습니다.

반례)

7 7 100
0 0 0 0 0 0 0
0 1 1 1 1 1 2
0 0 0 0 0 0 0
1 1 1 0 1 1 1
0 0 0 0 0 0 1
0 1 1 1 1 1 1
0 0 0 0 0 0 0

실제 반례입니다.

정답은 12인데, 2차원 배열로 isOk를 사용하면 18이 나와버립니다.

그럼 코드를 살펴보겠습니다

static int n,m,t;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static boolean[][][] visit;
static int[][] arr;
static int MAX = Integer.MAX_VALUE;
static Queue<Point> queue = new LinkedList<>();

dx, dy로 각각의 방향을 설정합니다.

3차원 배열의 visit을 이용하며 Queue의 Point타입은 4개의 파라미터를 사용합니다.

class Point{
    int x;
    int y;
    int gram;
    int sum;
    Point(int x, int y, int gram,int sum){
        this.x = x;
        this.y = y;
        this.gram = gram;
        this.sum = sum;
    }
}

gram도 받아주는 것이 좋습니다.

이런 과정을 오버로딩이라고 부릅니다.

Point 클래스를 이용하여 Point를 3가지 변수만 받게, 그 이하의 변수만 사용하게끔 만들 수 있는 것이 오버로딩의 장점이죠.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
t = scan.nextInt();
arr = new int[n][m];
visit = new boolean[n][m][2];
for(int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        arr[i][j] = scan.nextInt();
    }
}

n, m, t를 입력받고 arr, visit을 선언 후 arr도 입력받습니다.

bfs();
if(MAX == Integer.MAX_VALUE || MAX > t)
    System.out.println("Fail");
else
    System.out.println(MAX);

bfs()를 실행 후 다음의 조건에 따라 정답을 출력할 것입니다.

queue.offer(new Point(0,0,0,0));
visit[0][0][0] = true;

bfs내부 구조입니다.

제일 먼저 queue와 visit을 0을, true를 삽입합니다.

while(!queue.isEmpty()){
    Point now = queue.poll();
    if(arr[now.x][now.y] == 2)
        now.gram = 1;
    if(now.x == n - 1 && now.y == m - 1) {
        MAX = Math.min(now.sum, MAX);
        break;
    }

그리고 while문 안에서 갖고온 arr가 2면 now.gram을 1로 잡습니다.

또한 현재 갖고온 점이 목표 지점에 도달했을 때엔 (도달했을 순간엔 그 어떤 인덱스보다 t가 적으므로) MAX와 sum을 대소비교한 후 break합니다.

그리고 그러지 못할 경우엔 4가지 방향 매핑을 통해 탐색해야합니다.

int nx, ny;
    for(int i = 0; i < 4; i++){
        nx = now.x + dx[i];
        ny = now.y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m)
            continue;
        if(visit[nx][ny][now.gram])
            continue;
        if(now.gram == 0){
            if(arr[nx][ny] == 1)
                continue;
        }
        queue.offer(new Point(nx,ny,now.gram,now.sum + 1));
        visit[nx][ny][now.gram] = true;
    }
}

nx와 ny를 새로 이동한 점으로 잡습니다.

그리고 이 nx,ny가 0보다 작거나 n,m보다 크거나 같을 경우엔 passing해야 하며 방문한 인덱스일 경우에도 passing합니다.

그 외의 경우에는 얼마든지 탐색할 수 있어야합니다.

또한 now.gram이 0이면서 arr값이 1인 지점은 뚫을 수 없는 벽이므로 이 때에도 continue해주고 그 외의 경우에는 queue에 점을 담고 visit도 true로 바꾸어 줍니다.

이렇게 할 경우 visit배열을 검을 갖고 있을 때, 아닐 때를 구분 지어서 2가지 모두 다 고려해볼 수 있게됩니다.

다시 말해서 하나의 인덱스에 대해 2가지 경우의 수를 가진다고 이해하시면 되겠습니다.

감사합니다.