[C++] 파이프 옮기기 1 (백준 17070번)

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

 

그냥 bfs 해주되, 파이프가 놓여 있는 방향까지 큐에 넣도록 했다. 그래서 현 상태를 기준으로 어떻게 움직일 수 있는지를 체크해서 (n, n)에 도달하면 한번 카운트 해주는 식으로 구혔했다.

어차피 움직이는 방향이 무조건 오른쪽 또는 아래이기 때문에 시간 안에 해결 가능하다고 생각했는데, 제출해보니 좀 간당간당하고 dp로 풀어야 했던 문제인 듯하다. 

 

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

// 파이프가 놓여 있는 방향 {가로, 세로, 대각선}
int px[] = {0, -1, -1};
int py[] = {-1, 0, -1};

vector<vector<vector<int>>> d = {
    {{0, 1, 0}, {1, 1, 2}}, // 가로 상태일 때 이동할 수 있는 방법
    {{1, 0, 1}, {1, 1, 2}}, // 세로 상태일 때 이동할 수 있는 방법
    {{0, 1, 0}, {1, 0, 1}, {1, 1, 2}} // 대각선 상태일 때 이동할 수 있는 방법
};

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

    int n;
    cin >> n;

    vector<vector<bool>> a(n, vector<bool>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x == 1) a[i][j] = 1;
        }
    }

    queue<vector<int>> q;
    q.push({0, 1, 0});
    int ans = 0;
    
    while (!q.empty()) {
        int curi = q.front()[0];
        int curj = q.front()[1];
        int curs = q.front()[2];
        q.pop();
        if (curi == n - 1 && curj == n - 1) ans++;

        int kn = d[curs].size();
        for (int k = 0; k < kn; k++) {
            int nxti = curi + d[curs][k][0];
            int nxtj = curj + d[curs][k][1];
            int nxts = d[curs][k][2];
            if (nxti < n && nxtj < n && !a[nxti][nxtj]) {
                if ((nxts != 2) || ((!a[nxti - 1][nxtj]) && (!a[nxti][nxtj - 1]))) {
                    q.push({nxti, nxtj, nxts});
                }
            }
        }
    }

    cout << ans << '\n';
}

(AC)