[BOJ/백준 17070][C++] 파이프 옮기기 1

문제

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

백준 17070

백준 17070

백준 17070

 

문제 내용

(1,1), (1,2)에 걸쳐 가로로 놓여있는 파이프를 이동시켜 한쪽 끝이 (N, N)에 위치하게 하는 방법의 개수를 구하면 된다.

파이프는 한 번 이동할 때, 벽을 긁으면 안 되고 빈칸만을 차지해야 한다.

파이프는 밀면서 45도 회전이 가능하다. 또한, 밀 수 있는 방향은  →, ↘, ↓ 뿐이다.

 

문제 풀이

bfs를 사용하여 문제를 해결할 수 있다.

파이프가 가로로 위치했을 때는  →, ↘ 방향으로 이동할 수 있고,

세로로 위치했을 때는  ↘, ↓ 방향으로 이동할 수 있고,

대각선으로 위치했을 때는  →, ↘, ↓ 방향으로 이동할 수 있다.

즉, 우리는 매 순간 파이프가 놓여있는 방향과 좌표를 알아야 한다. 

 

bfs를 통해 각 칸에 갈 수 있으면 +1을 하면 된다.

 

코드

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

int n;
int arr[17][17];
int count[17][17]; // 파이프를 옮길 수 있는 방법 개수
queue<pair<int, pair<int, int>>> pipes;

bool isPossible(int r, int c) { return r >= 1 && c >= 1 && r <= n && c <= n; }

void moveHorizontal(int r, int c) {
    if (isPossible(r, c + 1) && arr[r][c + 1] == 0) {
        pipes.push({1, {r, c + 1}});
        count[r][c + 1]++;
    }
}

void moveVertical(int r, int c) {
    if (isPossible(r + 1, c) && arr[r + 1][c] == 0) {
        pipes.push({2, {r + 1, c}});
        count[r + 1][c]++;
    }
}

void moveDiagonal(int r, int c) {
    if (isPossible(r + 1, c + 1) && arr[r][c + 1] == 0 && arr[r + 1][c] == 0 && arr[r + 1][c + 1] == 0) {
        pipes.push({3, {r + 1, c + 1}});
        count[r + 1][c + 1]++;
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    pipes.push({1, {1, 2}});

    while (!pipes.empty()) {
        auto pipe = pipes.front();
        pipes.pop();

        int position = pipe.first;
        int r = pipe.second.first;
        int c = pipe.second.second;

        if (position == 1) { // 가로로 이동
            moveHorizontal(r, c);
            moveDiagonal(r, c);
        } else if (position == 2) { // 세로로 이동
            moveVertical(r, c);
            moveDiagonal(r, c);
        } else { // 대각선으로 이동
            moveHorizontal(r, c);
            moveVertical(r, c);
            moveDiagonal(r, c);
        }
    }

    cout << count[n][n];
}