백준 16954 - 움직이는 미로 탈출

Java

16954 번 - 움직이는 미로 탈출

문제

접근 방법

BFS의 응용문제 토마토의 접근법과 비슷하게 해결하였다.

BFS의 while 내부에 또 다른 while을 두어 2중 반복을 수행하였는데
이는 queue의 좌표가 먼저 움직이고 벽이 아래로 이동하기 때문에 먼저 큐의 크기만큼 반복한다.

이후 제자리에 머무는 경우를 포함하여 8방향으로 앞으로 다음 턴에 벽이 내려오지 않는다면, 그 좌표를 add하며 BFS로 원하는 목표 위치에 도달하는지 판별한다.

코드

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

public class Main {
	static int n, m, result;
	static char[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = 8;
    	
    	map = new char[n][n];
    	boolean[][] vis = new boolean[n][n];
    	
    	for(int i = 0; i < 8; i++)
    		map[i] = br.readLine().toCharArray();
    	
    	Queue<int[]> queue = new LinkedList<int[]>();
    	queue.add(new int[] {n - 1,0});
    	
    	int[] dy = {-1,-1,-1,0,0,1,1,1};
    	int[] dx = {-1,0,1,-1,1,-1,0,1};
    	
    	int[] q;
    	int y,x,ny,nx, chk_ny, count;
		// 한번 loop가 돌 때마다 벽이 내려온다.
    	quit : while(!queue.isEmpty()) {
    		count = queue.size();
    		vis = new boolean[n][n];
    		// 현재 이동할 좌표들의 개수만큼 반복
    		while(count-- != 0) {
    			q = queue.poll();
        		y = q[0];
        		x = q[1];
        		
        		// 바로 위에 돌이 없다면, 제자리에 한번 머문다.
        		ny = y - 1;  
        		nx = x;
        		if(isIn(ny,nx) && map[ny][x] != '#') {
        			queue.add(new int[] {y,x});
        		}
        		// 8방향 탐색
        		for(int i = 0; i < 8; i++) {
            		ny = y + dy[i];
            		nx = x + dx[i];
            		// 제일 위애 도달하면, 목표 위치까지 벽이 없으므로 도달 가능
            		if(ny == 0) {
            			result = 1;
            			break quit;
            		}
            		
            		chk_ny = ny - 1;
            		if(chk_ny < 0)
            			continue;
            		// 현재 위치에 이동할 수 있고, 이후 벽이 내려오지 않으면서 방문하지 않았으면
            		if(isIn(ny,nx) && map[chk_ny][nx] != '#' && !vis[ny][nx]) {
            			queue.add(new int[] {ny,nx});
            			vis[ny][nx] = true;
            		}
        		}
    		}
    		
			// 벽이 내려옴
    		for(int i = 7; i >= 1; i--) {
    			map[i] = map[i - 1].clone();
    		}
    		Arrays.fill(map[0], '.');
    	}
    	System.out.println(result);
    	br.close();
	}
	static boolean isIn(int y, int x) {
		if(0 <= y && y < n && 0 <= x && x < n && map[y][x] != '#')
			return true;
		return false;
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

방문 배열을 사용하지 않아도 해결 가능하지만, 쓰는 것이 시간 단축의 도움을 확인하였다.

개선할 점