(c++)백준 16954번: 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

[풀이]

bfs를 사용하였다.

check배열을 3차원으로 선언하고 초 단위로 해당 좌표에 방문한 적 있는지 표시 (check[n][x][y] == n초에 (x,y)좌표에 방문한 적 있는지)

욱제의 캐릭터가 (0,7)에 도달할 수 있는 조건

1. 맨 윗칸 어디든 도착할 수 있으면 (0,7)에도 도착할 수 있다. 더 이상 위에서 내려올 벽이 없기 때문!

2. 8초가 지난 후엔 남아 있는 벽이 없으므로 (0,7)에 도착할 수 있다.

 

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdio>//scanf
using namespace std;

struct Pos {
	int time;//몇 초 지났는지
	int x, y;
};

char Chess[8][8];
bool check[9][8][8];//n초 지났을 때 (x,y)좌표 방문했는지
const int dxy[][2] = { {-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1},{0,0} };

int bfs() {
	queue<Pos>q;
	q.push({ 0,7,0 });//0초에 (7,0)에서 출발
	check[0][7][0] = true;

	while (!q.empty()) {
		int t = q.front().time;
		int x = q.front().x;
		int y = q.front().y;
		q.pop();

		//말이 맨 위칸에 도달하면 (0,7)까지 갈 수 있다.
		if (x == 0)return 1;

		for (int i = 0; i < 9; i++) {
			int nx = x + dxy[i][0];
			int ny = y + dxy[i][1];
			int nt = t+1;
			//8초가 지난 후엔 남아있는 벽이 없으므로 (0,7)까지 갈 수 있다. 
			if (nt >= 8)
				return 1;

			if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8)
				continue;
			//가려는 칸에 벽이 있으면
			if (nx - t >= 0 && Chess[nx - t][ny] == '#')continue;
			//가려는 칸에 벽이 내려올 예정이면
			if (nx - t - 1 >= 0 && Chess[nx - t - 1][ny] == '#')continue;
			if (check[nt][nx][ny] == false) {
				check[nt][nx][ny] = true;
				q.push({ nt,nx,ny });
			}
		}
	}
	return 0;
}

void solution() {
	string s;
	for (int i = 0; i < 8; i++) {
		cin >> s;
		for (int j = 0; j < 8; j++) {
			Chess[i][j] = s[j];
		}
	}
	int ans = bfs();
	cout << ans << '\n';
}

int main() {
	solution();
	return 0;
}