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

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

16954번: 움직이는 미로 탈출

 

[문제 요약]

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

 

- 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다.

- 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

 

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

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

 

[문제 조건]

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

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

- 시간 제한 : 2초

- 메모리 제한 : 512MB

 

[문제 풀이]

이번 문제는 시뮬레이션의 관점을 살짝 바꿔서 생각하면 쉽게 풀리는 문제였다. 

 

이게 무슨 말이냐? 일반적으로 구현 or 시뮬레이션 문제로 생각한다면 매 초마다 캐릭터가 이동하고 , 벽이 내려오는 2개의 과정을 계속 반복하면서 우상단까지 도달할 수 있는지 확인하면 될 것이다. 하지만 이렇게하면 시간적으로나 메모리적으로나 오래걸리는 방법이다.

 

따라서 필자는 다음과 같은 방법으로 정답을 구하였다.

• 원소가 vector<int>인 2차원 배열을 이용하여 각 벽들이 각 지점에 몇초에 도달하는지 저장해준다. 밑에 예제의 경우 7번째 행의 2번째 열에는 0초, 2초에 벽이 존재함으로 wall_time[7][2] = [0,2] 가 저장되어 있을 것이다.
• 캐릭터는 상하좌우,대각선, 제자리 총 9개의 방향으로 이동하는데, 새로 이동할 지점에 같은 시간에 도달하는 벽이 있으면 이동하지 않는다.
• 제자리의 경우 방문여부를 무시하고 큐에 추가해준다.

........
........
........
........
........
.#......
#.......
.#......

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

int N = 8;
int dx[9] = { -1,0,1,-1,0,1,-1,0,1 };
int dy[9] = { -1,-1,-1,0,0,0,1,1,1 };
vector<vector<char>> mp(8, vector<char>(8,0));
vector<vector<vector<int>>> wall_time(8, vector<vector<int>>(8));
vector<pii> wall;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> mp[i][j];
			if (mp[i][j] == '#') wall.push_back({ i,j });
		}
	}

	//각 벽들이 위치별로 몇초에 도달하는지 저장
	for (int i = 0; i < wall.size(); i++)
	{
		int y = wall[i].first;
		int time = 0;
		for (; y < 8; y++)
		{
			wall_time[y][wall[i].second].push_back(time);
			time++;
		}
	}

	queue<pair<pii, int>> q;
	vector<vector<bool>> ck(8, vector<bool>(8, 0));
	ck[7][0] = true;
	q.push({ {7,0},0 });
	while (!q.empty())
	{
		pair<pii, int> tmp = q.front(); q.pop();

		if (tmp.first.first == 0 & tmp.first.second == 7)
		{
			cout << "1"; return 0;
		}
		for (int i = 0; i < 9; i++)
		{
        	//제자리의 경우
			if (i == 4)
			{
				bool flg = false;
				for (int k = 0; k < wall_time[tmp.first.first][tmp.first.second].size(); k++)
				{
					if (wall_time[tmp.first.first][tmp.first.second][k] == tmp.second + 1) { flg = true; break; }
				}
				if (!flg) q.push({ {tmp.first.first,tmp.first.second}, tmp.second + 1 });
				continue;
			}
			int nx = tmp.first.second + dx[i];
			int ny = tmp.first.first + dy[i];

			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			if (ck[ny][nx]) continue;
			bool flag = false;
			for (int k = 0; k < wall_time[ny][nx].size(); k++)
			{
				if (wall_time[ny][nx][k] == tmp.second || wall_time[ny][nx][k] == tmp.second+1) { flag = true; break; }
			}
            //이동이 불가능한경우 continue
			if (flag) continue;
			else
			{
				ck[ny][nx] = true;
				q.push({ {ny,nx} ,tmp.second + 1 });
			}
		}
	}
	cout << "0";
	return 0; 
}

이번 문제를 푸는데 있어서 실수하기 가장 쉬운 부분은 아마도 캐릭터가 상하좌우 대각선만 이동하는 것이 아니라 제자리에 있을 수 있는 선택지가 있기 때문에 문제를 잘 읽었어야 되는 문제였다.

굳