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

문제

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

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

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

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

 

입력

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

 

출력

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

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct pos
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}
};

int N;
vector< vector<int> > board;
vector<int> line;

bool bfs()
{
	queue<pos> q;
	pos curr, next;
	int dr[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
	int dc[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
	int i, j, size;

	// 출발지 삽입
	next.init(7, 0);
	q.push(next);
	while (!q.empty())
	{
		size = q.size();
		for (i = 0; i < size; i++)
		{
			curr = q.front();
			q.pop();
			// 목적지에 도착한 경우
			if (curr.r == 0 && curr.c == 7)
			{
				return true;
			}
			// 현재 위치로 벽이 떨어진 경우
			if (board[curr.r][curr.c])
			{
				continue;
			}
			// 상하좌우/대각선의 인접한 칸으로 이동하거나 제자리에 머무름
			// 범위를 벗어나거나 벽인 경우 이동하지 않음
			for (j = 0; j < 9; j++)
			{
				next.init(curr.r + dr[j], curr.c + dc[j]);
				if (next.r < 0 || next.r >= N || next.c < 0 || next.c >= N)
					continue;
				if (board[next.r][next.c])
					continue;
				q.push(next);
			}
		}
		// 미로가 움직임 = 벽이 떨어짐
		// 가장 위에 빈칸으로 이루어진 행을 삽입하고 가장 아래의 행을 삭제함
		board.insert(board.begin(), line);
		board.pop_back();
	}
	return false;
}

int main()
{
	int i, j;
	string s;

	N = 8;
	for (i = 0; i < N; i++)
	{
		cin >> s;
		for (j = 0; j < N; j++)
		{
			if (s[j] == '.')
				line.push_back(0);
			else
				line.push_back(1);
		}
		board.push_back(line);
		line.clear();
	}
	line.resize(8, 0);
	cout << bfs() << endl;
	return 0;
}

 

링크

16954번: 움직이는 미로 탈출

inbdni/Baekjoon