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

https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

---

문제

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

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

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

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

입력

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

출력

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

---

#include <iostream>
#include <queue>
using namespace std;

//상하좌우, 대각선, 제자리
int dx[9] = {1,-1,0,0,1,1,-1,-1,0};
int dy[9] = {0,0,1,-1,-1,1,-1,1,0};

char map[8][8];
bool visit[8][8][20];

struct group
{
	int row;
	int col;
	int count; // count에 따라 캐릭터가 이동하고 벽이 내려옴
};

void bfs()
{
	queue<group> q;
	q.push({7,0,0});
	visit[7][0][0] = true;
	while (!q.empty())
	{
		int nowX = q.front().row;
		int nowY = q.front().col;
		int nowCount = q.front().count;
		q.pop();
		for (int i = 0; i < 9; i++)
		{
			int nextX = nowX + dx[i];
			int nextY = nowY + dy[i];
			if (nextX == 0 && nextY == 7)//다음 칸이 목표 칸이면
			{
				cout << 1;
				return;
			}
			if (visit[nextX][nextY][nowCount + 1])
				continue;
			//범위 벗어나면 스킵
			if (nextX < 0 || nextX >= 8 || nextY < 0 || nextY >= 8)
				continue;
			//가려는 칸이 벽이라면 스킵
			if (map[nextX - nowCount][nextY] == '#' && nextX - nowCount >= 0)
				continue;
			//이동한다음 벽을 마주친다면
			if (map[nextX - nowCount - 1][nextY] == '#' && nextX - nowCount - 1 >= 0)
				continue;
			//위 조건들에 해당 안된다면
			visit[nextX][nextY][nowCount + 1] = true;
			q.push({ nextX, nextY, nowCount + 1 });
		}
	}
	cout << 0;
}

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

	bfs();
}