[알고리즘] Java / 백준 / 움직이는 미로 탈출 / 16954

[알고리즘] Java / 백준 / 움직이는 미로 탈출 / 16954

문제

문제 링크

접근 방식

체스판이 8*8로 크기가 고정되어있고 1초마다 벽이 아래로 내려가므로 결국 8초 후엔 체스판에 벽이 없어진다.

따라서 욱제가 움직이면서 8초만 버틴다면 게임을 승리하는 것이다.

1. 각 초에 대한 맵의 상태를 3차원 배열로 표현한다. (map[0][3][0] ⇒ 0초에 3행 0열의 상태)
2. 욱제의 위치인 7행 0열에서 dfs를 시작하여 9 방향( 그대로 포함 ) 으로 이동한다.
3. 이동할 때 시간을 늘려 해당 시간대의 맵에서 벽과 겹치는지 확인한다.
4. 0초에서 7초까지 살아남아 8초가 된 dfs가 존재하면 answer 을 1로 바꾼다. (answer 초기값 = 0)
5. 모든 dfs가 실행된 후 answer을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_16954 {

	static char[][][] map;
	static int[][] deltas = {{0,0},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
	static int answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 시간이 흐른 각 초당 체스판의 상태(8초 이후엔 벽이 없다)
		map = new char[8][8][8];
		
		for(int i=0;i<8;i++) {
			String line = br.readLine();
			for(int j=0;j<8;j++) {
				char c =line.charAt(j);
				if(c == '#') {
					for(int k=0;k<8;k++) {
						if(i+k <8) map[k][i+k][j] ='#'; 
					}
				}
			}
		}
		
		answer = 0;
		
		dfs(7,0,0);
		System.out.println(answer);
	}
	
	// 욱제 이동
	static void dfs(int r, int c, int t) {
		// 8초를 버티면 게임 승리
		if(t == 8) {
			answer = 1;
			return;
		}
		// 벽이 내려온 상태의 맵에서 벽과 위치가 동일 == 부딪힘
		if(map[t][r][c] == '#') {
			return;
		}
		
		for(int i=0;i<9;i++) {
			int nR = r + deltas[i][0];
			int nC = c + deltas[i][1];
			
			// 맵을 벗어나거나 벽으로 이동할 수 없음
			if(nR<0||nR>=8||nC<0||nC>=8||map[t][nR][nC]=='#') continue;
			dfs(nR,nC,t+1);
		}
	}
	
}