[BOJ]16954 - 움직이는 미로 탈출(그래프 탐색 - bfs, dfs)

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

16954번: 움직이는 미로 탈출

- 좀 특이한 그래프 탐색 문제여서 기록해둔다. 미로벽이 아래 방향으로 움직이는 경우의 수를 따로 메모리를 할당해서 저장하는 것이 아니고 시간이 1초 지날 때마다 아래 방향으로 1씩 움직이는 것을 이용해서 지금 캐릭터의 있는 위치의 t초 전, t+1초 전의 위치가 벽인지를 체크하는 방식으로 짤 수 있다. 이를 배열로 표현하면 a[nx-t][ny], a[nx-t-1][ny] 가 벽인지를 체크하는 방식으로 표현할 수 있다. 

- 8초 이후까지 캐릭터가 살아남는다면 벽이 모두 사라져있으므로 무조건 미로의 (0,7)에 도달할 수 있다.

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

const int dx[9] = {1, 1, 1, 0, -1, -1, -1, 0, 0};
const int dy[9] = {-1, 0, 1, 1, 1, 0, -1, -1, 0};

string a[8];
bool visit[8][8][9];  // 0~8초 까지 카운트

bool bfs() {
    queue<tuple<int, int, int>> q;  // r,c,t
    visit[7][0][0] = true;          // 시작
    q.push({7, 0, 0});

    while (!q.empty()) {
        int x, y, t;
        tie(x, y, t) = q.front();
        q.pop();
        if ((x == 0 && y == 7) || t == 8) return true;

        for (int i = 0; i < 9; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nt = t + 1;

            if (0 > nx || 0 > ny || nx >= 8 || ny >= 8) continue;
            if (nx - t >= 0 && a[nx - t][ny] == '#') continue;
            if (nx - t - 1 >= 0 && a[nx - t - 1][ny] == '#') continue;
            if (!visit[nx][ny][nt]) {
                visit[nx][ny][nt] = true;
                q.push({nx, ny, nt});
            }
        }
    }

    return false;
}

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

    for (int i = 0; i < 8; ++i) {
        cin >> a[i];
    }

    if (bfs())
        cout << 1;
    else
        cout << 0;

    return 0;
}

f