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

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

16954번: 움직이는 미로 탈출

 

bfs(너비 우선 탐색)을 이용해 문제를 해결하는데, 이때 벽이 어디까지 내려왔는지 확인해야 하므로, bfs를 확인하는 discovered에 위치뿐만이 아니라, 벽들이 얼마큼 내려온 상태까지 확인하여, discovered[행][열][현재 벽들이 얼마큼 내려왔는지(depth)] = (확인한적 없을 때:0, 확인한적 있을 때:1)를 저장하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

deque<string> board;
int dxdy[9][2] = { {0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };
int discovered[10][10][10]; //[행][열][현재 벽들이 얼만큼 내려왔는지] 
queue<pair<pair<int, int>, int>> q;

int solve(pair<int, int> start) {

	discovered[start.first][start.second][0] = 1;
	q.push(make_pair(start, 0));

	while (!q.empty()) {
		pair<int, int> here = q.front().first;
		int here_depth = q.front().second;
		q.pop();

		//벽이 캐릭터가 있는 칸으로 이동 했을때
		if (here.first - here_depth >= 0 && board[here.first - here_depth][here.second] == '#') {
			continue;
		}

		//도착지에 도착 했을때
		if (here.first == 0 && here.second == 7) {
			return 1;
		}

		for (int dir = 0; dir < 9; dir++) {
			pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
			int there_depth;

			if (here_depth == 8) { //벽들이 다 내려온 상태일때
				there_depth = 8;
			}
			else {
				there_depth = here_depth + 1;
			}

			//범위를 넘어가지 않는지 확인
			//방문한적 없던 상황인지 확인
			if (there.first >= 0 && there.first < 8 && there.second >= 0 && there.second < 8 && discovered[there.first][there.second][there_depth] == 0) {

				//움직이려는 위치가 빈칸인지 확인
				if ((there.first - here_depth < 0) || (there.first - here_depth >= 0 && board[there.first - here_depth][there.second] == '.')) {
					discovered[there.first][there.second][there_depth] = 1;
					q.push(make_pair(there, there_depth));
				}

			}
		}
	}

	return 0;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	for (int i = 0; i < 8; i++) {
		string row;
		cin >> row;

		board.push_back(row);
	}

	cout << solve(make_pair(7, 0));

	return 0;
}