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

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

17070번: 파이프 옮기기 1

<풀이>

1. 집의 상태를 입력받는다.

2. 파이프를 한쪽 끝으로 옮길 수 있는 방법의 수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 방법의 수를 구해야하므로, 파이프를 놓는 모든 경우를 다 해보아야합니다. 따라서, 저는 백트래킹을 선택하였습니다.(파이프를 놓을 수 있는 유망한 경우에만 탐색할 것이므로)

 

2. 파이프 옮기기

=> 파이프는 종류에 따라 (1)다음에 놓을 파이프가 다르고, (2)파이프를 놓을 수 있는 공간이 다릅니다. 따라서, 저는 위 두가지 경우를 배열로 미리 만들어 놓았습니다.(코드의 connect[][]와 check[][] 참조)

 

3. 최적화 할 수 있을까?

=> 이 문제는 작은 부분 문제에서 구한 최적의 답을 이용해서 큰 문제의 최적의 답을 구할 수 있습니다. 따라서, 저는 DP를 이용하여 최적화 하였습니다.

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int dx[] = { 0,1,1 };
int dy[] = { 1,0,1 };
int connect[3][3] = { //파이프 끼리 연결 가능 여부
    {1,0,1},          
    {0,1,1},
    {1,1,1},
};
int check[3][3] = { //파이프를 놓을 때, 확인해야하는 부분
    {1,0,0},
    {0,1,0},
    {1,1,1}
};
 
int N;
int map[16][16];
int cache[16][16][3];
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    return true;
}
 
bool canMove(int x, int y, int type) {
    for (int i = 0; i < 3; i++) {
        if (!check[type][i]) continue;
 
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (!isInner(nx, ny) || map[nx][ny] == 1) return false;
    }
    return true;
}
 
int movePipe(int x, int y, int type) {
 
    if (x == N - 1 && y == N - 1) return 1;
 
    int& ret = cache[x][y][type];
    if (ret != -1) return ret;
 
    ret = 0;
    for (int i = 0; i < 3; i++) {
        if (connect[type][i] && canMove(x, y, i)) {
            ret += movePipe(x + dx[i], y + dy[i], i);
        }
    }
    return ret;
}
 
void solution() {
    answer = movePipe(0, 1, 0);
}
 
int main() {
    //초기화
    N = 0;
    memset(map, 0, sizeof(map));
    memset(cache, -1, sizeof(cache));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

백트래킹과 DP에 대해 알아볼 수 있는 문제였습니다.