백준(BOJ) 16954번 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

풀이 :

 

시간이 8초부터는 벽은 모두 내려간 상태고.(점)만 남은 상태가 된다. 이 상태에서는 무조건

 

목표지점(0,7)까지 갈수 있다.

 

따라서 3차원 배열 [시간][y좌표][x좌표] 로 bfs를 처리하자.

 

q에 담을 때에는 벽이라서 못가는 경우와 내려오는 벽에 닿는 경우는 걸러주어야 한다.

 

코드 ( C++ )

 

	#include <iostream>
	#include <string>
	#include <cstring>
	#include <queue>
	#include <tuple>
	using namespace std;
	string a[8];
	const int dy[9] = { -1,0,1,1,1,0,-1,-1,0 };
	const int dx[9] = { 1,1,1,0,-1,-1,-1,0,0 };
	bool check[9][8][8];
	int main()
	{
	for (int i = 0; i < 8; ++i)
	cin >> a[i];
	queue<tuple<int,int,int>> q;
	q.push({ 0,7,0 });
	check[0][7][0] = true;
	int ans = 0;
	while (!q.empty()) {
	int t,y,x;
	tie(t,y,x) = q.front();
	q.pop();
	if (y == 0 && x == 7) ans = 1;
	for (int i = 0; i < 9; ++i) {
	int ny = y + dy[i];
	int nx = x + dx[i];
	int nt = min(t + 1, 8);
	if (!(0 <= ny && ny < 8 && 0 <= nx && nx < 8)) continue;
	// 벽이라서 못갈때
	if (ny - t >= 0 && a[ny - t][nx] == '#') continue;
	// 내려올 벽이 닿았을때
	if (ny - t - 1 >= 0 && a[ny - t - 1][nx] == '#') continue;
	if (!check[nt][ny][nx]) {
	check[nt][ny][nx] = true;
	q.push({ nt,ny,nx,});
	}
	}
	}
	if (ans) cout << 1 << "\n";
	else cout << 0 << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub