Baekjoon 17070번 파이프 옮기기 1

문제

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

걸린 시간

00 : 26 : 18

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
vector<vector<int>> house;

int solve(int lr, int lc, int rr, int rc){
    // 기저 사례
    if(rr == n-1 && rc == n-1) return 1;
    // 재귀 호출
    int ret = 0;
    if(lr == rr){ // horizontal
        if(rc+1 < n)
            if(house[rr][rc+1] != 1)
                ret += solve(lr, lc+1, rr, rc+1);
        if(rr+1 < n && rc+1 < n)
            if(house[rr][rc+1] != 1 && house[rr+1][rc+1] != 1 && house[rr+1][rc] != 1)
                ret += solve(lr, lc+1, rr+1, rc+1);
    }
    else if(lc == rc){ // vertical
        if(rr+1 < n)
            if(house[rr+1][rc] != 1)
                ret += solve(lr+1, lc, rr+1, rc);
        if(rr+1 < n && rc+1 < n)
            if(house[rr][rc+1] != 1 && house[rr+1][rc+1] != 1 && house[rr+1][rc] != 1)
                ret += solve(lr+1, lc, rr+1, rc+1);
    }
    else{ // diagonal
        if(rc+1 < n)
            if(house[rr][rc+1] != 1)
                ret += solve(lr+1, lc+1, rr, rc+1);
        if(rr+1 < n)
            if(house[rr+1][rc] != 1)
                ret += solve(lr+1, lc+1, rr+1, rc);
        if(rr+1 < n && rc+1 < n)
            if(house[rr][rc+1] != 1 && house[rr+1][rc+1] != 1 && house[rr+1][rc] != 1)
                ret += solve(lr+1, lc+1, rr+1, rc+1);
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    house.resize(n, vector<int>(n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> house[i][j];
    cout << solve(0, 0, 0, 1);
    return 0;
}

집의 크기가 최대 16x16 이고 이동시킬 수 있는 경우의 수가 파이프 방향에 따라 최대 3개로 작아, dfs 로 모든 경우를 탐색해보았더니 ac를 받았다.

분류에 "다이나믹 프로그래밍" 가 있는걸 보면 다음 단계의 파이프 옮기기 문제에서는 n의 크기가 클 것 같아 보인다.