[BOJ] 16954 움직이는 미로 탈출

문제: www.acmicpc.net/problem/16954

 

<조건>

• 8×8인 체스판에서 탈출하는 게임
• 체스판의 모든 칸은 빈칸(.) 또는 벽(#) 중 하나이다.
• 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.
• 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다.
• 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.
• 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
• 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

 

문제 풀이:

• 8*8 체스판이 1초마다 한 칸씩 내려간다.
• 매 초마다 직접 벽들을 내려가게 구현하는 것 대신 
• 입력을 (8,0)~(15,7) 범위에 받고, 윗부분은. 또는 여백으로(벽이 아닌 칸) 둔다.
• 그리고 매 초마다 보는 범위를 위로 올려나가면 된다.
• 즉, 맨 처음 접하는 테이블의 범위는 (8,0)~(15,7)
  • 1초 뒤는 (7,0)~(14,7))
• 즉, 캐릭터는 (7,0)에서 시작해서 (0,7)에 도달하게 한다는 것만 생각하고
  • 맵을 볼 때는 arr[8+x-time][y]로 생각하면 된다.
• bfs를 돌 때, 현재 queue 사이즈를 기록하고 그만큼만 돌리면 시간에 따라 캐릭터를 이동시킬 수 있다.
• 매 시간에 따라, 맵이 달라지기 때문에, visit 체크를 하지 않았다.
  • 처음에 위치(x,y)와 시간으로 visit 체크를 했더니 56%에서 틀렸었다 ㅠ
  • 8초 후부터는 맵이 고정되기 때문에 그때부터 visit 체크를 해줌으로써 속도를 향상할 수 있겠지만, 크기가 8*8로 작기 때문에, 이 부분은 고려하지 않았다.
• 다른 문제들과 달리, 대각선으로 갈 수도, 정지할 수도 있기 때문에 조건을 주의해서 읽자!

(0,0)							(0,7)
(7,0)							(7,7)
(8,0)							(8,7)
(15,0)							(15,7)

 

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

typedef pair<int, int> P;
int dx[9] = { -1,-1,0,1,1,1,0,-1,0 };
int dy[9] = { 0,1,1,1,0,-1,-1,-1,0 };
char arr[20][20];
bool visit[8][8][100];

bool func() {
	queue<P> q;
	q.push({ 7,0 });

	int time = 0;
	while (!q.empty()) {
		int sz = q.size();

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

			if (arr[8+curX-time][curY] == '#') continue; // 벽이 캐릭터가 있는 칸으로 이동한 경우 -> 더 이상 이동 불가

			for (int d = 0; d < 9; d++) {
				int x = curX + dx[d];
				int y = curY + dy[d];
				if (x < 0 || x >= 8 || y < 0 || y >= 8) continue;
				if (arr[8 + x - time][y] == '#') continue;

				if (x == 0 && y==7) return true;

				q.push({ x,y });
			}
		}
		if (time < 8) time++;
	}
	return false;
}

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

	for (int i = 8; i <16; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> arr[i][j];
		}
	}
	cout<<func();

	return 0;
}