움직이는 미로 탈출

📍 문제 설명

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

16954번: 움직이는 미로 탈출

 

💡 접근

q사이즈만큼 루프를 돌린다음 벽을 내려한다!

해당 조건이 없으면 한 칸을 이동할 때 마다 벽이 내려가게 됨

방문조건을 고려하려면 q사이즈 루프돌때마다 새로 방문 배열을 만들어줘야 했는데 딱히 고려안해도 메모리, 시간초과가 나지는 않았다.

 

👩‍💻 코드

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

public class Main {
    static int[] arr, dx = {-1,1,0,0,-1,-1,1,1,0}, dy = {0,0,-1,1,-1,1,-1,1,0};
    static char[][] board;
    static boolean[][] visited;
    static int n, m, k, t, num, cnt, second;
    static ArrayList<Integer> list = new ArrayList<>();

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

        //StringTokenizer st = new StringTokenizer(br.readLine());
        //n = Integer.parseInt(st.nextToken());
        //m = Integer.parseInt(st.nextToken());
        board = new char[8][8];
        visited = new boolean[8][8];
        for(int i = 0; i < 8; i++) {
            String s = br.readLine();
            for(int j = 0; j < 8; j++) {
                board[i][j] = s.charAt(j);
            }
        }

        if(bfs()) System.out.println(1);
        else System.out.println(0);

    }

    private static boolean bfs() {
        Queue<Point> q = new LinkedList<>();

        q.add(new Point(7, 0));

        while (!q.isEmpty()) {
            int len = q.size();
            for(int k = 0; k < len; k++) {
                Point cp = q.poll();
                if (cp.x == 0 && cp.y == 7) return true;
                //현 위치가 벽이면 더이상 못감
                if (board[cp.x][cp.y] == '#') continue;

                //욱제 이동
                for (int i = 0; i < 9; i++) {
                    int nx = cp.x + dx[i];
                    int ny = cp.y + dy[i];

                    if (nx<0 || ny<0 || nx>=8 || ny>=8 || board[nx][ny]=='#') continue;
                    q.offer(new Point(nx, ny));
                }
            }
            //벽 아래로 내리기
            for (int i = 7; i >= 0; i--) {
                for (int j = 0; j < 8; j++) {
                    //벽 아래로 내리기 -> 내린 벽의 위치 = 욱제 위치 이면 더 이상 이동 불가
                    if (board[i][j] == '#') {
                        board[i][j] = '.';
                        if (i == 7) continue;
                        board[i + 1][j] = '#';
                    }
                }
            }
            cnt++;
        }
        return false;
    }


    private static class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}