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

백준(BOJ) 16954 움직이는 미로 탈출

 

난이도
221221 기준 골드 3

사용 알고리즘
백트래킹
시뮬레이션

문제 링크
https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

 

입력

 8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

 

출력

 욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

 

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 문제에서 원하는 답은 욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있는지 없는지 여부입니다. 욱제가 오른쪽 윗 칸에 몇 초만에 갈 수 있는지는 전혀 관심사가 아니기 때문에 욱제가 오른쪽 윗칸에 도착하지 못하는 경우만 생각해보겠습니다.

 욱제의 캐릭터가 있는 곳에 벽이 이동하는 경우에만 욱제는 탈출에 실패합니다.

 그런데 8X8 체스판이기에 8초 후에는 모든 벽이 사라지게 되네요. 그럼 8초동안 벽이 이동하고 그 후에도 욱제의 캐릭터가 살아있는 경우가 있다면 욱제는 무조건 오른쪽 윗칸에 도착할 수 있지 않을까요?

 한 번의 이동은 9개의 경우의 수가 있기에 9^8 = 43,046,721의 경우의 수에 벽에 부딪혀 사라지는 경우 백트래킹까지 되므로 시간초과도 없을 것 같네요

 

3. 풀이 구상

 

 욱제의 9방향으로 이동시키고 벽을 움직이는 것을 8초까지 반복하고 아직 살아있는 욱제의 캐릭터가 있으면 성공 없다면 실패로 코드를 짜보겠습니다

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

// 백준 16954번 움직이는 미로 탈출
public class Main {

	static int[][] board;
	
	// 가운데, 위부터 시계방향
	static int[] dr = {0,-1,-1,0,1,1,1,0,-1};
	static int[] dc = {0,0,1,1,1,0,-1,-1,-1};
	
	static class Wookjae {
		
		int r;
		int c;
		
		public Wookjae(int r, int c) {
			this.r = r;
			this.c = c;
		}
		
		boolean move(int direction) {
			this.r = this.r + dr[direction];
			this.c = this.c + dc[direction];
			
			if(this.r >= 0 && this.r < 8 && this.c >= 0 && this.c < 8) {
				return true;
			} else {
				return false;
			}
		}
		
	}

    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    	board = new int[8][8];
    	
    	for(int r = 0; r < 8; r++) {
    		String str = br.readLine();
    		for(int c = 0; c < 8; c++) {
    			if(str.charAt(c)=='.') {
    				board[r][c] = 0;
    			} else if(str.charAt(c)=='#') {
    				board[r][c] = 1;
    			}
    		}
    	}
    	
    	// 욱제는 왼쪽 아래에서 시작
    	Wookjae wj = new Wookjae(7,0);
    	isPossible = false;
    	moveWall(wj,0);
    	if(isPossible) {
    		bw.write("1");
    	} else {
    		bw.write("0");
    	}
    	
    	bw.flush();
        bw.close();
        br.close();
    }
    
    static boolean isPossible;
    
    static void moveWall(Wookjae wj, int time) {
    	// 기저조건 벽이 욱제랑 만나면 return;
    	// time만큼 욱제의 r을 -1 시켜서 벽이 이동하는 것 처럼 만들 것
    	// wj.r-time이 0보다 작다는 것은 벽을 안만난 다는 뜻
    	if((wj.r-time)>=0 && board[wj.r-time][wj.c]==1) {
    		return;
    	}
    	
    	// 8초가 되었는데 벽이 욱제랑 만나지 않았다면 true로 바꾸고 return;
    	if(time == 8) {
    		isPossible = true;
    		return;
    	}
    	
    	// true인게 하나라도 나오면 전부 리턴
    	if(isPossible) {
    		return;
    	}
    	
    	
    	// 유도파트
    	for(int i = 0; i <= 8; i++) {
    		Wookjae nextWookjae = new Wookjae(wj.r,wj.c);
    		
    		// 넥스트 욱제가 inRange라면
    		if(nextWookjae.move(i)) {
    			// 벽으로 이동하려하면 continue
    			if((nextWookjae.r-time)>=0 && board[nextWookjae.r-time][nextWookjae.c]==1) {
    				continue;
    			}
    			moveWall(nextWookjae, time+1);
    		}
    	}
    	
    	
    }

}

 

 

2. 주의할 점

 

 벽이 이동할 때마다 벽을 전부 이동시키는 것 보다 현재 캐릭터의 위치에서 지나간 시간 초만큼 캐릭터의 r값을 -1*초 시켜주고 그 위치에 벽이 있는지를 확인하는 것이 시간적으로 훨씬 빠른 방법이라 생각합니다.

 

 

풀이 후기

 깔끔하게 풀려서 기분이 좋네요 처음 생각대로 문제가 술술 풀리면 이렇게 상쾌할 수가 없습니다.