[BOJ] 17070 - 파이프 옮기기 1

기존 파이프가 놓여있는 상태에 따라 파이프를 미는 방법이 정해져 있고, 그 경로 상 벽이 있는 경우 밀지 못한다.

이 상황에서 파이프를 끝까지 밀 수 있는 경우의 수를 구하는 문제이다.

문제 해결 전략
경우의 수를 구하는 문제이므로 현재 파이프의 상태에서 밀 수 있는 모든 경우를 queue에 집어 놓고 bfs를 통해 풀었다.

예를들어 현재 가로 상태라면 오른쪽 칸이 비어 있을 경우 밀 수 있기 때문에 큐에 삽입하고, 대각선으로 밀기 위해 오른쪽, 대각선 아래, 아래 방향이 모두 비어 있을 경우 역시 밀 수 있으므로 큐에 삽입 한다.

이런식으로 bfs를 통해 문제를 해결하였다.

대각선으로 미는 경우는 가로, 세로, 대각선 상태에서 모두 진행 가능하므로 이 부분에 대해서는 갈 수 있는 좌표를 배열에 저장해서 3번의 반복문을 통해 한번에 검사하였다.

코드

#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[17][17];
int xp[3] = {0,1,1};
int yp[3] = {1,1,0};
queue<pair<pair<int,int>,pair<int,int>>> q;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

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

    q.push(make_pair(make_pair(1,1), make_pair(1,2)));

    int cnt = 0;
    while(!q.empty()){
        int sx = q.front().first.first;
        int sy = q.front().first.second;
        int ex = q.front().second.first;
        int ey = q.front().second.second;
        q.pop();

        //cout << sx << " " << sy << " " <<ex << " " << ey << "\n";
        if(ex == n && ey == n)
            cnt++;

        if(sx == ex){ // 가로
            if(arr[ex][ey+1] == 0 && ey+1 <= n)
                q.push(make_pair(make_pair(ex,ey), make_pair(ex,ey+1)));
        }
        else if(sy == ey) { // 세로
            if(arr[ex+1][ey] == 0 && ex+1 <= n)
                q.push(make_pair(make_pair(ex,ey), make_pair(ex+1,ey)));
        }
        else if(sx == ex-1 && sy == ey-1) { // 대각선
            if(arr[ex][ey+1] == 0 && ey+1 <=n)
                q.push(make_pair(make_pair(ex,ey), make_pair(ex,ey+1)));
            if(arr[ex+1][ey] == 0 && ex+1 <=n)
                q.push(make_pair(make_pair(ex,ey), make_pair(ex+1,ey)));
        }

        int flag = 0;
        for(int i=0;i<3;i++){
            if(flag == 1)
                break;
            int x = ex + xp[i];
            int y = ey + yp[i];
            if(arr[x][y] == 1 || x > n || y > n)
                flag = 1;
        }
        if(flag == 0)
            q.push(make_pair(make_pair(ex,ey), make_pair(ex+1,ey+1)));
    }

    cout << cnt << "\n";
    return 0;
}

생각해볼 점
이전의 경로가 다르더라도 현재 파이프의 상태가 같을 수 있다. 그냥 bfs를 하면 이런 경우 중복 탐색을 하게 되어서 시간이 좀 걸릴 수 있다.

이런 문제를 해결하기 위해 dp를 사용하여 상태를 저장한 후 만약 같은 상태에 도달하면 그냥 +1만 해 주고 그 부분에 대해서는 탐색을 중지하면 시간을 좀 더 아낄 수 있을 것이다.

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