[C/C++] 백준 - 16954번 : 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

문제

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

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

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

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

입력

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

출력

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

 

제일 아래 왼쪽 칸에서 제일 위 맨 오른쪽 칸으로 도달할 수 있는지 확인하면 되는 문제이다.

BFS로 갈 수 있는 지역을 확장시켜주면 되지만, 나름 까다로웠던 문제이다.

 

우선, 욱제의 이동이 먼저 이루어지고 이동이 끝나면 그 때 벽이 한 칸씩 아래로 내려온다.

욱제가 이동할 수 있는 구역은 (양옆,위아래 + 대각선 방향 4가지 + 제자리)로 총 9가지가 있다.

* 여기서 생각해야할 것이 이동가능한 구역으로 이동을 시켰는데 이동이 끝난 후, 벽이 덮쳐서 다음에는 그 지역에서 다른 지역으로 이동이 불가능한 곳이 될 수도 있다. 이 부분은 맵의 초기화 상태를 보고 현 위치에 벽이 덮혔는지 아닌지 확인하고 진행해주면 된다.

 

그리고 욱제를 이동시킬 때, 욱제의 방문여부를 확인하지 않고 갈 수 있는 지역은 모조리 큐에 넣고 BFS를 진행하는 완전탐색 기법으로 해결하려해도 이 문제의 맵 최대 크기가 8이고, 시간제한이 2초이기 때문에 문제를 통과할 수는 있다.

하지만 방문여부를 표시해주면 0ms로 효율적인 코드가 될 수 있다. 단, 방문처리를 할 때 생각해야할 것이 제자리에 있는 것도 이동경로 중 하나가 되기 때문에 이 부분을 생각해서 처리를 해주어야한다.

 

욱제의 이동이 끝나면 벽의 이동이 시작된다.

나는 벽의 이동을 구현하는 부분에서 벽의 위치에 따라 우선순위를 두고 이동시켰다. (아래쪽에 있는 벽부터 아래로 이동)

 

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 987654321
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

typedef struct Node {
	int y;
	int x;
}Node;

pl End;
queue<pl> Cur;
vector<pl> Block;
bool visited[9][9];
const Node Direct[] = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1},{0,0} };
int adj[8][8];
bool isCan = false;

bool cmp(pl a, pl b) {
	if (a.first == b.first) return a.second < b.second;
	else return a.first < b.first;
}

int isValid(int y, int x) {
	return (0 <= y && y < 8 && 0 <= x && x < 8);
}

void Input_Data() {
	for (int i = 0; i < 8; i++) {
		string s; cin >> s;
		for (int j = 0; j < s.size(); j++) {
			if (s[j] == '.') adj[i][j] = 0;
			else if (s[j] == '#') {
				adj[i][j] = -1;
				Block.push_back({ i, j });
			}
		}
	}
	Cur.push({ 7,0 });
	visited[7][0] = true;
	End.first = 0, End.second = 7;
}

void Move() {
	int n = Cur.size();
	for (int i = 0; i < n; i++) {
		int y = Cur.front().first;
		int x = Cur.front().second;
		visited[y][x] = false;
		Cur.pop();
		if (adj[y][x] == -1) continue;
		for (int i = 0; i < 9; i++) {
			int ny = y + Direct[i].y;
			int nx = x + Direct[i].x;

			if (isValid(ny, nx)) {
				if (ny == End.first && nx == End.second) {
					isCan = true;
					break;
				}
				if (!visited[ny][nx] && adj[ny][nx] == 0) {
					visited[ny][nx] = true;
					Cur.push({ ny, nx });
				}
			}
		}
		if (isCan) break;
	}
}

void Block_Down() {
	int N = Block.size();
	vector<pl> Temp;
	sort(Block.begin(), Block.end(), cmp);
	for (int i = 0; i < N; i++) {
		int y = Block.back().first;
		int x = Block.back().second;
		Block.pop_back();
		adj[y][x] = 0;

		int ny = y + 1;
		int nx = x;
		if (!isValid(ny, nx)) continue;
		adj[ny][nx] = -1;
		Temp.push_back({ ny,nx });
	}
	Block = Temp;
}

void go() {
	if (isCan) return;
	if (Cur.empty()) return;
	Move();
	Block_Down();
	go();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	Input_Data();
	go();

	int Answer = 0;
	if (isCan) Answer = 1;
	cout << Answer << endl;

	return 0;
}