[알고리즘] cpp 파이프 옮기기

포인트

1. 시작 지점을 0,1 로 설정을 해야 하는 부분

2. 대각선, 오른쪽, 아래 방향이 전부 수가 다름

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

queue<tuple<int, int, int>> q;
int map[17][17];

int n = 0;
int dx[] = {0, 1, 1}; // row, col, cross
int dy[] = {1, 0, 1}; // row, col, cross

int bfs(int a, int b, int c) {
    int count = 0;
    q.push(make_tuple(a, b, c));
    while (!q.empty()) {
        int x, y, dir;
        tie(x, y, dir) = q.front();
        q.pop();

        if (x == n - 1 && y == n - 1) //끝까지 오면
            count++;

        for (int i = 0; i < 3; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int ndir = i;

            if (ndir + dir == 1) continue; // (row to col) or (col to row) 서로 직각 상황은 나올 수 없다.ㄴ

            if (nx >= n || ny >= n) continue;
            if (map[nx][ny] == 1) continue;

            if (i == 2) { // cross
                if (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1) continue;

                q.push(make_tuple(nx, ny, ndir));
            } else {
                q.push(make_tuple(nx, ny, ndir));
            }
        }
    }
    return count;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];

    cout << bfs(0, 1, 0); //출력 //끝자리에서 출력이 편하다'
    //문제의 조건 처음 파이프는 1, 1, 1, 2를 지난다
}