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

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

---

[ 알고리즘풀이 ]

DP 문제로 3차원 DP 배열을 이용하면 문제를 해결할 수 있습니다.

파이프는 두 칸을 차지하지만, 우리는 파이프의 끝이 (N, N)에 도달하면 되므로 파이프 끝에만 집중하면 됩니다.

 

DP[0][X][Y] : (X, Y) 지점에 가로 상태의 파이프 끝이 올 수 있는 경우의 수

DP[1][X][Y] : (X, Y) 지점에 세로 상태의 파이프 끝이 올 수 있는 경우의 수

DP[2][X][Y] : (X, Y) 지점에 대각선 상태의 파이프 끝이 올 수 있는 경우의 수 라고 정의해보겠습니다.

 

그러면 다음과 같은 점화식과 초깃값이 성립합니다.

 

- DP[0][1][2] = 1 ( 처음에 파이프가 가로로 놓여있으므로 )

- DP[0][X][Y] = DP[0][X][Y - 1] + DP[2][X][Y - 1]

- DP[1][X][Y] = DP[1][X - 1][Y] + DP[2][X - 1][Y]

- DP[2][X][Y] = DP[0][X - 1][Y - 1] + DP[1][X - 1][Y - 1] + DP[2][X - 1][Y - 1]

 

 가로 상태로 (X, Y) 지점에 파이프 끝이 올 수 있는 경우는 가로 상태 (X, Y - 1) 지점에서 미는 경우와, 대각선 상태(X, Y - 1) 지점에서 미는 경우뿐이다.

 세로 상태로 (X, Y) 지점에 파이프 끝이 올 수 있는 경우는 세로 상태(X - 1, Y) 지점에서 미는 경우와, 대각선 상태(X - 1, Y) 지점에서 미는 경우뿐이다.

 대각선 상태로 (X, Y) 지점에 파이프 끝이 올 수 있는 경우는 가로, 세로, 대각선 상태(X - 1, Y - 1) 지점에서 미는 경우다.

 

 점화식은 간단하지만, check 해줘야 하는 조건이 있다.

 파이프를 옮길 때, 꼭 빈칸이어야 되는 부분 가로, 세로, 대각선마다 다르므로 check 함수를 이용해 따로 조건을 걸어줘야 한다.

#include<iostream>

int N, map[17][17] = {}, dp[3][17][17] = {};

using namespace std;

bool check(int x, int y) {
	if (1 <= x && x <= N && 1 <= y && y <= N && map[x][y] == 0)
		return true;
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	dp[0][1][2] = 1;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++) {
			if (check(i, j - 1) && check(i, j))
				dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];
			if (check(i - 1, j) && check(i, j))
				dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];
			if (check(i - 1, j - 1) && check(i - 1, j) && check(i, j - 1) && check(i, j))
				dp[2][i][j] += dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
		}
	}
	cout << dp[0][N][N] + dp[1][N][N] + dp[2][N][N];

	return 0;
}

---