백준 16954번 움직이는 미로 탈출

문제

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

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

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

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

입력

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

출력

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

 

BFS 턴제 -> size 만큼만 작업하고 행렬 내리기 

 

#include<iostream>
#include <string.h>
#include<string>
#include<queue>
#include <vector>
#include<map>

using namespace std;

char arr[8][8];
bool visit[8][8];

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

void moveDown()
{

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

}


int main(void)
{
	
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			cin >> arr[i][j];
		}
	}

	queue<pair<int, int> >  que;
	que.push({ 7,0 });
	
	while (1)
	{
		
		int size = que.size();
		if (!size)
		{
			break;
		}

		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < size; i++)
		{
			int y = que.front().first;
			int x = que.front().second;
			que.pop();

			if (y == 0 && x == 7)
			{
				cout << 1 << endl;
				return 0;
			}

			if (arr[y][x] == '#')
			{
				continue;
			}

			for (int j = 0; j < 9; j++)
			{
				int newy = y + dy[j];
				int newx = x + dx[j];
				if (newy >= 0 && newy < 8 && newx >= 0 && newx < 8)
				{
					if (!visit[newy][newx] && arr[newy][newx] != '#')
					{
						visit[newy][newx] = true;
						que.push({ newy,newx });
					}
				}
			}

		}
		moveDown();
		
		
	}

	cout << 0 << endl;
	return 0;
}