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

17070번: 파이프 옮기기 1

알고리즘 분류에 dp가 포함되어 있지만 dp를 활용하지 않고 문제를 풀었다. bfs를 이용하여 답을 구했다. 큐에 현재 위치와 파이프 방향을 저장하고 반복문을 돌면서 (N-1,N-1)에 도달하는 개수를 저장하여 출력하였다. 파이프는 오로지 5시 방향으로 가로, 세로, 대각선으로만 연결되기에 지나갔던 위치를 다시 지나가지 않는다. 그래서 따로 지나갔던 자리를 저장하지 않았다.
bfs로 생각보다 간단하게 풀려 빠르게 풀 수 있었다.

#include <iostream>
#include <queue>

using namespace std;

int N, res = 0;
int A[16][16];
int dy[3] = { 0,1,1 };
int dx[3] = { 1,1,0 };

void bfs() {
    queue<pair<pair<int, int>, int>> q;     // 0 : 가로, 1 : 대각선, 2 : 세로

    q.push({ {0,1}, 0 });

    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int dir = q.front().second;

        q.pop();

        if (y == N - 1 && x == N - 1) {
            res++;
            continue;
        }

        for (int i = 0; i < 3; i++) {
            if (dir == 0 && i == 2) continue;
            if (dir == 2 && i == 0) continue;

            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (A[ny][nx] == 1) continue;
            if (i == 1 && (A[ny - 1][nx] == 1 || A[ny][nx - 1] == 1)) continue;

            q.push({ {ny,nx},i });
        }
    }
}

void solution(){
    bfs();

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}