[BOJ - JAVA] 16954 - 움직이는 미로 탈출 (BFS)

# 주소

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

16954번: 움직이는 미로 탈출

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Main{
    static int[][] arr = new int[8][8];
    static boolean isOk = false;
    static int dir[][] = {{-1,0}, {-1,1}, {0,1}, {0,0},{1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}};
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 8; i++){
            String str = scan.next();
            for(int j = 0; j < 8; j++){
                if(str.charAt(j) == '.')
                    arr[i][j] = 0;
                else
                    arr[i][j] = 1;
            }
        }
        queue.offer(new Point(7,0));
        while(!queue.isEmpty() && !isOk){
            bfs();
            move();
        }
        if(isOk)
            System.out.println(1);
        else
            System.out.println(0);
    }
    static void bfs(){
        int size = queue.size();
        for(int k = 0; k < size; k++){
            if(isOk)
                return;
            Point now = queue.poll();
            if(arr[now.x][now.y] == 1)
                continue;
            if(now.x == 0 && now.y == 7) {
                isOk = true;
                return;
            }
            for(int i = 0; i < 9; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= 8 || ny >= 8)
                    continue;
                if(arr[nx][ny] == 1)
                    continue;
                queue.offer(new Point(nx,ny));
            }
        }
    }
    static void move(){
        for(int i = 6; i >= 0; i--){
            for(int j = 0; j < 8; j++){
                if(arr[i][j] == 1){
                    arr[i + 1][j] = 1;
                    arr[i][j] = 0;
                }
            }
        }
    }
}

주인공이 먼저 이동하고 미로가 한 칸씩 아래로 내려오며 벽을 피해서 이동해야 하는 문제입니다.

또한 8x8 크기의 체스판에서 이동이 이루어지고 상,하,좌,우를 포함하여 대각선의 움직임도 합산해서 풀어야 합니다.

따라서 전 Queue를 사용하여 이동을 진행하겠습니다.

static int[][] arr = new int[8][8];
static boolean isOk = false;
static int dir[][] = {{-1,0}, {-1,1}, {0,1}, {0,0},{1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}};
static Queue<Point> queue = new LinkedList<>();

dir[][]은 안움직이고 가만히 있는 것도 포함하기 때문에 {0,0}도 넣었습니다.

Scanner scan = new Scanner(System.in);
for(int i = 0; i < 8; i++){
    String str = scan.next();
    for(int j = 0; j < 8; j++){
        if(str.charAt(j) == '.')
            arr[i][j] = 0;
        else
            arr[i][j] = 1;
    }
}

arr배열은 int타입의 2차원 배열로 선언할 것입니다.

char타입이면 보기 어려워서 .이 들어오면 0을 넣고 그 외의 것이 들어오면 1을 넣어서 0은 공간, 1은 벽을 의미합니다.

queue.offer(new Point(7,0));
while(!queue.isEmpty() && !isOk){
    bfs();
    move();
}
if(isOk)
    System.out.println(1);
else
    System.out.println(0);

왼쪽 젤 아래에서 시작하므로 (7,0)을 queue에 넣고 while문을 실행합니다.

bfs내부구조를 살펴보겠습니다.

int size = queue.size();
for(int k = 0; k < size; k++){
    if(isOk)
        return;
    Point now = queue.poll();
    if(arr[now.x][now.y] == 1)
        continue;
    if(now.x == 0 && now.y == 7) {
        isOk = true;
        return;
    }

size는 queue의 크기입니다.

이 size를 변수에 꼭 담아서 사용해야합니다.

안그러면 queue의 크기만큼 계속 탐색하면서 for문을 돌리기 때문에 총체적 난국이 펼쳐집니다..

따라서 queue의 크기를 size에 꼭 담아서 사용하시고, isOk가 true가 되면 return하여 메모리 낭비를 줄입니다.

isOk는 목표지점에 도달했을 때 true로 바꿀 boolean타입입니다.

Point now = queue.poll();
if(arr[now.x][now.y] == 1)
    continue;
if(now.x == 0 && now.y == 7) {
    isOk = true;
    return;
}

따라서 Point now를 가져와서 arr가 1이면 continue;하고 0,7에 도달하면 isOk는 true, return하여 bfs문을 빠져나옵니다.

for(int i = 0; i < 9; i++){
    int nx = now.x + dir[i][0];
    int ny = now.y + dir[i][1];
    if(nx < 0 || ny < 0 || nx >= 8 || ny >= 8)
        continue;
    if(arr[nx][ny] == 1)
        continue;
    queue.offer(new Point(nx,ny));
}

그리고 for문을 9번 돌려서 탐색합니다.

이 구문 때문에 앞에서 size를 변수로 담아야 하는 것입니다.

nx,ny를 새로 탐색할 점으로 선언합니다.

이후 이 점의 범위를 정하고 빈 공간일 때에만 queue에 점을 삽입합니다.

계속 반복하여 bfs문을 마칠 수 있겠습니다.

static void move(){
    for(int i = 6; i >= 0; i--){
        for(int j = 0; j < 8; j++){
            if(arr[i][j] == 1){
                arr[i + 1][j] = 1;
                arr[i][j] = 0;
            }
        }
    }
}

move()함수는 다음과 같습니다.

6,0부터 한 행식 벽이 있는 지점으 인덱스를 한 칸 내려서 arr[i+1][j] = 1로 바꾸고 원래의 arr[i][j] = 0으로 바꾸는 작업을 하여 벽을 내릴 수 있습니다.

이것 역시 bfs()문이 실행될 때마다 move()함수도 한 번씩 실행되어야 하기 때문에 while문으로 표현하여 둘 다 한 번씩 실행하게 도모해야 합니다.

감사합니다.