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

문제

 

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

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

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

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

입력

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

출력

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

 

---

 

풀이

 

1초가 지날 때마다 다음과 같은 일이 발생한다.

• 캐릭터가 벽이 아닌 곳으로 움직임
• 모든 벽이 한 줄씩 내려옴

 

캐릭터가 갈 수 있는 방향은 제자리에 머무르는 것까지 총 9가지이다.

 

움직일 때 고려해야 할 사항은, 벽이 있는 자리로는 움직이지 못한다는 것과 해당 시간에 다른 좌표에서 먼저 방문을 한 곳은 중복으로 방문을 하지 않아야 하는 것이다.

 

 

 

다음으로 벽이 움직일 경우에는, 가장 아랫줄의 벽은 사라지게 되고 나머지 벽들을 한 줄씩 내려오게 된다.

 

이 때, 벽이 내려오게 된다면 해당 위치에 있는 캐릭터는 이동할 수 없게 되므로 사라지게 된다.

 

따라서 캐릭터가 움직일 때 해당 좌표가 벽이라면 움직일 수 없도록 확인을 해야한다.

 

---

 

코드

#include <iostream>
#include <queue>

#define SIZE 8

using namespace std;

char board[9][9];
queue<pair<int, int>> q;

int dir[9][2] = { {0,1},{0,-1}, {1,0}, {-1,0}, {-1,-1}, {1,1}, {-1,1}, {1,-1}, {0, 0} };

void input();
bool ch_move();
void wall_move();

int main() {
	input();

	q.push(make_pair(0, 7));

	while (true) {
		if (q.size() == 0) {
			cout << 0 << "\n";
			break;
		}
		if (ch_move()) {
			cout << 1 << "\n";
			break;
		}
		wall_move();
	}

	return 0;
}

void input() {
	for (int i = 0; i < SIZE; i++) {
		cin >> board[i];
	}
}

bool ch_move() {
	int qsize = q.size();
	bool visit[SIZE + 1][SIZE + 1] = { false, };

	for (int i = 0; i < qsize; i++) {
		int curX = q.front().first;
		int curY = q.front().second;
		q.pop();

		if (board[curY][curX] == '#')
			continue;

		if (curX == 7 && curY == 0)
			return true;


		for (int j = 0; j < 9; j++) {
			int nextX = curX + dir[j][0];
			int nextY = curY + dir[j][1];

			if (0 <= nextX && nextX < SIZE && 0 <= nextY && nextY < SIZE) {
				if (board[nextY][nextX] != '#' && !visit[nextY][nextX]) {
					q.push(make_pair(nextX, nextY));
					visit[nextY][nextX] = true;
				}
			}
		}
	}

	return false;
}

void wall_move() {
	for (int i = 0; i < SIZE; i++) {
		board[7][i] = '.';
	}

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