[알고리즘] c++ cpp 파이프시리즈 (파이프옮기기1)

포인트

1. bfs를 이해하고 있는가?

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[3] = {0, 1, 1}; //3방향으로 지나간다.
int dy[3] = {1, 0, 1};
 
int bfs(int a, int b, int c) {
    int count = 0;
 
    q.push ({ 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 += 1;
 
        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) {
                //대각선 상황에서
                if (map[nx - 1][ny] != 1 && map[nx][ny - 1] != 1) {
                    //걸치지 않으면 된다.
                    q.push ({ nx, ny, ndir });
                }
            }
            else {
                q.push ({ 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]; //map 을 입력한다. 
 
    cout << bfs(0, 1, 0); // 문제 조건 파이프 가로를 함으로
}