BOJ - 16954번 움직이는 미로 탈출 (C++)

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

문제 난이도

Gold 5

문제 접근법

BFS로 푸는데 대신 벽의 조건을 잘 봐야한다. 처음에는 구현 문제인 줄 알고 접근했다가 안 풀려서 꽤나 시간이 걸렸다.
시작은 맨 끝 줄에 있는 0행에서 시작하기 때문에 -1해서 전 줄에 있는 벽을 구분한다. 벽과 만날 것 같으면 continue, 또 다음 벽으로 내려올 벽과 만나면 continue 해준다.
여기서 중요한점은 방향이 상하좌우, 대각선 뿐만 아니라 현재 위치도 챙겨야한다!

통과 코드

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

using namespace std;

vector<string> arr;
int dy[9][2] = { {1,0},{-1,0},{0,-1},{0,1},{1,1},{1,-1},{-1,1},{-1,-1}, {0,0} };
bool ch[9][8][8];

int main() {
	for (int i = 0; i < 8; i++) {
		string str;
		cin >> str;
		arr.push_back(str);
	}
	queue<tuple<int, int, int>> q;
	q.push({ 7,0,0 });
	ch[0][7][0] = true;
	int ans = 0;
	while (!q.empty()) {
		int x, y, stage;
		tie(x, y, stage) = q.front();
		q.pop();
		if (x == 0 && y == 7) {
			ans = 1;
		}
		for (int i = 0; i < 9; i++) {
			int nx = x + dy[i][0];
			int ny = y + dy[i][1];
			int nStage = min(stage + 1, 8);
			if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8 || ch[nStage][nx][ny]) continue;
			if (nx - stage >= 0 && arr[nx - stage][ny] == '#') continue;
			if(nx-stage-1>=0 && arr[nx-stage-1][ny] == '#') continue;
			ch[nStage][nx][ny] = true;
			q.push({ nx,ny,nStage });
		}
	}
	cout << ans;
	return 0;
}