[Java/자바 백준 16954] 움직이는 미로 탈출

풀이

8X8 맵에서 캐릭터는 인접한 곳 8방향 탐색과 제자리에 위치할 수 있습니다.

턴마다 캐릭터가 먼저 이동하고 난 뒤, 벽들이 아래로 떨어집니다.

 

저는 dfs로 진행하면서

1. 8방향 탐색으로 빈칸(.)의 위치를 찾고

2. 빈칸 위치 바로 위가 벽(#)이라면 continue

3. dfs로 진행하므로 다른 방향 탐색할 때 영향을 주면 안되므로 값을 copy했습니다.

    copy 과정에서 

 

시간을 줄이기 위해서 flag를 사용해서 true면 리턴시켰고

벽이 아래로 떨어지게 되면 빈칸이 맨 윗줄에 생기므로

캐릭터가 row = 0 에 도달하게되면 flag = true 로 처리했습니다.

 

 

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

public class Main {
	static char[][] map = new char[8][8];
	static boolean flag;
	// 북 북동 동 남동 남 남서 서 북서 제자리
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1, 0};
	static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1, 0};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int i = 0 ; i < 8 ; i++) {
			String input = br.readLine();
			for(int j = 0 ; j < 8 ; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		
		game(0, 7, 0, map);
		if(flag == true) System.out.println(1);
		else System.out.println(0);
	}
	
	// 캐릭터 - > 벽
	private static void game(int cnt, int x, int y, char[][] map) {
		if(cnt == 8) {
			flag = true;
			return;
		}
		
		if(flag == true) return;
		
		for(int i = 0 ; i < 9 ; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(0 > nx || nx >= 8 || 0 > ny || ny >= 8 || map[nx][ny] == '#') continue;
			
			// 가능한지 체크 
			if(nx - 1 < 0) {
				flag = true;
				return;
			}
			if(map[nx-1][ny] == '#') continue;
			
			// copy
			char[][] copy = new char[8][8];
			for(int index = 0 ; index < 8 ; index ++) {
				copy[index] = map[index].clone();
			}
			
			// 중력 
			for(int col = 0 ; col < 8 ; col ++) {
				for(int row = 6 ; row >= 0 ; row --) {
					copy[row + 1][col] = copy[row][col];
				}
				copy[0][col] = '.';
			}
			game(cnt + 1, nx, ny, copy);
		}
		return;
	}
}