boj, 백준) 16954. 움직이는 미로 탈출 ( C / C++)

1. 문제 링크

www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

2. 문제 개요

8x8인 체스판에서 탈출하는 게임을 만들었다. 벽이 있는데 벽은 욱제가 움직일 때마다 밑으로 한 칸씩 움직인다. 욱제가 벽에 깔리면 게임은 끝난다. 욱제는 가만히 있거나 상하좌우 대각선으로 모두 9가지로 움직일 수 있다. 

욱제의 캐릭터가 가장 왼쪽 아래에서 가장 오른쪽 위까지 이동할 수 있는지 없는지 구해보자.

 

3. 문제 힌트

시간개념을 더해보는 건 어떨까?

0초일 때 캐릭터가 있을 수 있는 위치.. 1초일 때 캐릭터가 있을 수 있는 위치.. 2초일 때...

---

 

특별한 방법을 생각하지 않고 단순하게 생각하면 이 문제의 경우 왔던 곳을 또 갈 수 있기 때문에, 대략 9^8가지의 경우를 모두 살펴봐야 한다. 당연히 시간 초과.

 

4. 문제 풀이

처음에 시간 개념을 더하지 않고 어떻게 시간 내에 왔던 곳을 또 가면서.. 문제를 풀 수 있을까에 꽂혀서 시간을 좀 썼다. 문제를 조금 다르게 생각해서 문제 힌트에서 적었던 것처럼,

0초일 때 캐릭터가 서 있을 수 있는 위치, 1초일 때 캐릭터가 서 있을 수 있는 위치.. 등을 고려해서 한 번  다 같이 움직이고 BFS방문 배열을 초기화하는 그러한 방법으로 문제를 풀었다. 

 

BFS를 할 때 조건은 움직이려는 칸의 위칸에 벽이 있으면 안 되고 (깔리니까)

8번 이상 움직이면 벽이 없기 때문에 더 이상 BFS 탐색을 하지 않아도 도착할 수 있다.

 

n=8이라고 했을 때, 시간 개념을 넣어서 BFS를 하면 반복마다 한 칸을 움직이고 움직이는 것을 최대 8번을 하게 되니 O(8n^2)이 되겠다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

struct COORD {
	int y, x, time;
};

char map[8][8];
bool visited[8][8];
const int dx[] = { 0,1,1,0,-1,-1,-1,0,1 };
const int dy[] = { 0,0,-1,-1,-1,0,1,1,1 };

void _move()
{
	for (int j = 0; j < 8; ++j)
		map[7][j] = '.';

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

	return;
}

int main()
{
	for (int i = 0; i < 8; ++i)
		scanf("%s", map[i]);

	COORD start;
	start.x = start.time = 0;
	start.y = 7;

	queue<COORD> q;
	q.push(start);
	visited[start.y][start.x] = true;

	while (!q.empty())
	{
		//시간 별
		int len = q.size();
		memset(visited, false, sizeof(visited));

		for (int i = 0; i < len; ++i)
		{
			COORD cur = q.front(); q.pop();
			if (cur.time >= 8 || (cur.x == 7 && cur.y == 0)) {
				printf("1\n");
				return 0;
			}
			for (int dir = 0; dir < 9; ++dir) {

				COORD next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.time = cur.time + 1;

				if (next.y < 0 || next.x < 0 || next.x >= 8 || next.y >= 8 || visited[next.y][next.x] || map[next.y][next.x] == '#')
					continue;

				if (next.y >= 1 && map[next.y - 1][next.x] == '#')
					continue;

				visited[next.y][next.x] = true;
				q.push(next);
			}
		}
		_move();
	}
	printf("0");

	return 0;
}

6. 결과