[백준/c++] 16954 움직이는 미로 탈출

문제

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

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

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

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

입력

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

출력

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

구현해야할 조건

간단한 시뮬레이션 게임이다. 1초동안 욱제의 캐릭터가 8방향중 이동할 수 있는 곳으로 이동이 가능한데, 일단 8군데 다 이동을 해보고 '#'이 있는 곳이나 범위를 벗어나면 이동이 불가능하고, 욱제가 있는 곳이 '#'이 되었다면 이동 또한 불가능하다. 이점을 유의하고 천천히 구현해보자! 항상 천천히! 

code

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

#define MAX 9

using namespace std;

const int dy[9] = {1,1,1,0,0,-1,-1,-1,0};
const int dx[9] = {-1,0,1,-1,1,-1,0,1,0};

char board[MAX][MAX];
queue<pair<int,int> > wj;

bool move()
{
	
	int wj_size = wj.size();
	bool visited[MAX][MAX];
	
	memset(visited,0,sizeof(visited));
	
	for(int i = 0; i < wj_size; i++)
	{
		int y = wj.front().first;
		int x = wj.front().second;
		wj.pop();
		
		if(board[y][x] == '#') // 이동 시작하려는 자리가 벽이라면? 움직이지 못한다! 이점 유의!!! 
			continue;
		
		if(y == 0 && x == 7) // 목적지에 도착하면 true 
			return true;
			
		for(int j = 0; j < 9; j++)
		{
			int ny = y + dy[j];
			int nx = x + dx[j];
			
			if(board[ny][nx] == '#')
				continue;
				
			if(0 <= nx && nx < 8 && 0 <= ny && ny < 8)
			{
				if(board[ny][nx] != '#' && !visited[ny][nx])
				{
					wj.push({ny,nx});
					visited[ny][nx] = true;
				}
			}
		}
	}
	
	return false; // 아직 목적지에 도착하지 못했다면 false 
}

void block_move()
{
	for(int i = 0; i < 8; i++)
		board[7][i] = '.';
		
	for(int i = 7; i > 0; i--)
	{
		for(int j = 0; j < 8; j++)
		{
			if(board[i-1][j] == '#')
			{
				board[i][j] = '#';
				board[i-1][j] = '.';
			}
		}
	}	
	
}

int main()
{
	
	for(int i = 0; i < 8; i++)
		cin >> board[i]; 
	
	wj.push({7,0});
	
	while(1)
	{
		if(wj.size() == 0)
		{
			cout << 0 << "\n";
			break;
		}
		if(move())
		{
			cout << 1 << "\n";
			break;
		}
		
		block_move();
		
	}
	
	return 0;
}