[BJ] 백준 16954 움직이는 미로 탈출 (JAVA)

문제

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

 

 

풀이 방법

가장 왼쪽 하단에서 가장 오른쪽 상단으로이동하면 되는 문제이다.
대신에 맵에는 벽이 존재하고 벽이 아래로 이동하는 조건이 걸려있다.
풀이 방법은 BFS로 풀이했다. 우선 이동 가능한 좌표들을 선언해주고(제자리 포함), 이동 가능한 구역으로 이동후 queue에 넣어준다.
그리고 방문배열을 체크해줘야하는데 제자리에 있는 경우도 있기 때문에 3차원 배열로 만들어서 마지막은 방향으로 방문 배열을 생성해줬다.
그리고 캐릭터 이동 -> 벽 이동이기 때문에 같은 횟수? 번째? 이동인 경우에는 한 번에 처리해주고 그 다음에 벽을 이동해줬다.

 

제출 코드

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

public class BOJ_16954_움직이는미로탈출 {
	public static void main(String[] args) throws IOException {
		int[][] move = {{1,0},{1,-1},{-1,0},{-1,-1},{0,1},{1,1},{0,-1},{-1,1},{0,0}};
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[][] map = new char[8][8]; //벽과 빈칸의 정보 저장
		for (int i = 0; i < 8; i++) {
			map[i] = br.readLine().toCharArray();
		}
		//시작 위치는 7,0 도착 위치는 0,7 
		int si = 7, sj = 0;
		boolean flag = false; //도착 가능 여부
		Queue<int[]> que = new LinkedList<int[]>();
		que.add(new int[] {si,sj});
		boolean[][][] visit = new boolean[8][8][9]; //방문 배열
		while(!que.isEmpty()) {
			int s = que.size();
			for (int p = 0; p < s; p++) {
				int[] t = que.poll();
				if(t[0]==0 && t[1]==7) { //도착 위치에 도달하면 flag 변경 후 break;
					flag = true;
					break;
				}
				if(map[t[0]][t[1]]=='#') continue; //벽이 있다면 캐릭터 이동 불가
				for (int k = 0; k < 9; k++) {
					int ni = t[0]+move[k][0];
					int nj = t[1]+move[k][1];
					if(ni>=0 && ni<8 && nj>=0 && nj<8 
							&& !visit[ni][nj][k] //해당 방향으로 방문체크
									&& map[ni][nj]=='.') { //빈칸인지 체크
						visit[ni][nj][k] = true;
						que.add(new int[] {ni,nj});
					}
				}
			}
			//벽 이동
			for (int i = 6; i >=0; i--) { //아래행으로 한칸씩 이동
				for (int j = 0; j < 8; j++) {
					map[i+1][j] = map[i][j];
				}
			}
			for (int j = 0; j < 8; j++) { //첫번째 행은 빈칸으로 
				map[0][j] = '.';
			}
		}
		if(flag) System.out.println(1);
		else System.out.println(0);
	}
}