백준 17070번: 파이프 옮기기 1

문제

문제 바로가기> 백준 17070번: 파이프 옮기기 1

풀이

파이프의 위치만 체크해가며 dfs 탐색을 진행하면 쉽게 풀 수 있는 문제이다. 그런데 나는 처음에 검사 전에 파이프 이동 성공 여부를 체크해서 틀렸다,, home[y][x]가 1일 수도 있고 대각선으로 온 경우 주변이 1일 수도 있으니까 검사가 먼저 필요하다!!!! (나만 바보 같이 틀린 것 같지만,, ㅎㅎ)

dfs를 이용한 풀이

#include<iostream>
#define MAX_N 17
using namespace std;

int N, ans = 0;
int home[MAX_N][MAX_N]; // 집의 상태

void dfs(int y, int x, int state){
    if(N<x || N<y || home[y][x] || (state==2 && (home[y-1][x] || home[y][x-1]))) // 범위를 벗어난 경우, 벽이 있는 경우
        return;
    if(x==N && y==N){ // 파이프 이동 성공
        ans++;
        return;
    }
    if(state==0){ //가로 
        dfs(y, x+1, 0);
        dfs(y+1, x+1, 2);
    }
    else if(state==1){ //세로
        dfs(y+1, x, 1);
        dfs(y+1, x+1, 2);
    }
    else if(state==2){ //대각선
        dfs(y, x+1, 0);
        dfs(y+1, x, 1);
        dfs(y+1, x+1, 2);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++) cin >> home[i][j];
    }
    dfs(1, 2, 0); // (1, 2) , 가로
    cout << ans;
}

그리고 이 문제는 (N, N)에 도착하는 방법이 가로, 세로, 대각선 3가지 방법이 있다는 점을 이용해서 dp를 이용해서도 풀 수 있다.3차원 array(행, 열, (가로,세로,대각선)) => int dp[17][17][3]를 선언해서 dp[1][2][0]=1로 놓고 dp를 진행하면 된다. dp를 이용하는게 시간이 훨씬 절약된다!

dp를 이용한 풀이

#include<iostream>
#include<cstring>
#define MAX_N 17
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int home[MAX_N][MAX_N], dp[MAX_N][MAX_N][3];
    memset(dp, 0, sizeof(dp)); // 초기화 
    dp[1][2][0]=1; // 초기화 
    
    int N; cin>>N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++) cin >> home[i][j];
    }
    for(int i=1; i<=N; i++){ // dp (반복문을 돌면서 값을 하나씩 update해나감)
        for(int j=3; j<=N; j++){
            if(home[i][j]) continue;
            dp[i][j][0] = dp[i][j-1][0]+dp[i][j-1][2]; // 가로
            dp[i][j][1] = dp[i-1][j][1]+dp[i-1][j][2]; // 세로
            if(!home[i-1][j] && !home[i][j-1]) // 대각선의 경우 추가 검사 필요
                dp[i][j][2] = dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j-1][2]; // 대각선
            else dp[i][j][2]=0;
        }
    }
    cout << dp[N][N][0] + dp[N][N][1] + dp[N][N][2]; // 가로, 세로, 대각선 도착 가짓수을 모두 더하면 총 도착 가짓수
}