[백준] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

DP를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 문제에서 주어진 규칙대로 파이프를 움직여서 파이프의 한쪽 끝이 가장 오른쪽 아래에 올 때까지 이동시켜야 합니다. 이 때, 목표 지점에 도달할 수 있는 경우의 수를 return 해야하는 문제입니다.

 

<Solution>

특정 칸에 도달할 때, 어떤 방식을 통해 도달하는지를 이용해 dp table을 구성하면 됩니다. 

 

무슨 이야기인지 그림으로 좀더 자세하게 살펴보면, 

다음의 색칠된 부분에 도달해야 하는 경우를 생각해봅시다. 

해당 블록에 도달하기전 파이프들의 위치는 다음과 같이 총 7가지 위치가 가능합니다.

 

이 상황에서 잘 생각해보면, 우리가 도달해야 하는 색칠된 부분을 (r,c)라고 가정하면, (r,c-1)의 지점에 도달하는 전체 경우의 수가 아닌 (r,c-1)에 가로로 도달하거나, 대각선으로 도달하는 경우에만 다음에 색칠된 (r,c) 지점에 도달할 수 있음을 알 수 있습니다. 

 

이처럼 각각의 칸에 어떻게 도달하였는지 방향과 방법 이렇게 두가지 정보를 모두 저장하면서 dp를 해야하는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다. 

 

#include <iostream>
// for debug
// #define debug

using namespace std;

char house[20][20];
int house_size;
int dp_table[3][20][20]; // 0->가로, 1->세로, 2->대각선
// direction, row, column

void getinput(){
    cin >> house_size;
    for(int i = 1; i<=house_size; i++){
        for(int j = 1; j<=house_size; j++){
            cin >> house[i][j];
        }
    }
}

bool can_move(int r, int c){
    return (house[r][c] == '0' && house[r-1][c] == '0' && house[r][c-1] == '0');
}

int solution(){
    // initialize dp
    dp_table[0][1][2] = 1; 

    // fill out dp
    for(int r = 1; r<=house_size; r++){
        for(int c = 2; c<=house_size; c++){
            if(r == 1 && c== 2) continue;
            if(house[r][c] == '1') continue;
            dp_table[0][r][c] = dp_table[0][r][c-1] + dp_table[2][r][c-1];
            dp_table[1][r][c] = dp_table[1][r-1][c] + dp_table[2][r-1][c];
            
            // check if we can move pipe
            dp_table[2][r][c] += (can_move(r,c)) ? dp_table[0][r-1][c-1] + dp_table[1][r-1][c-1] + dp_table[2][r-1][c-1] : 0;
        }
    }

    #ifdef debug
    // print dp table
    for(int i = 1; i<=house_size; i++){ 
        for(int j = 1; j<=house_size; j++){
            cout << dp_table[0][i][j] << dp_table[1][i][j] << dp_table[2][i][j] << ' ';
        }
        cout << endl;
    }
    #endif

    return dp_table[0][house_size][house_size] + dp_table[1][house_size][house_size] + dp_table[2][house_size][house_size];
}


int main(){

    getinput();

    #ifdef debug
    // for debug print house
    for(int i = 1; i<=house_size; i++){
        for(int j = 1; j<=house_size; j++){
            cout << house[i][j] << ' ';
        }
        cout << endl;
    }
    #endif

    cout << solution() << endl;

    return 0;


}