백준 No.17070 [파이프 옮기기 1]

No.17070 [파이프 옮기기 1]

---

  문제 

17070번: 파이프 옮기기 1 (acmicpc.net)

17070번: 파이프 옮기기 1

---

  설명 

  동적할당(DP : Dynamic programming) 을 이용하여 풀 수 있는 문제이다. 점화식을 위한 dp 배열은 3차원으로 선언을 하였다.

 

dp[ i ][ j ][ k ] == (i, j) 좌표로 오는 파이프가 k 방향에서 올 수 있는 경우의 수

(k == 1 인 경우는 좌측, k == 2 인 경우는 위, k == 3 인 경우는 좌측 대각선에 해당)

 

  좌표는 제일 좌측의 제일 상단을 (1, 1) 로 두고 for (int i = 1 ~ n) for (int j = 2 ~ n) 으로 풀었다. j 값에 1을 하지 않은 이유는, 시작부터 (1, 1) ---> (1, 2) 를 잇는 파이프가 있기때문에 ( i, 1 ) | 2 <= i 좌표로 올 수 있는 경우는 없기 때문이다.

 

  1. 해당 위치에 좌측에서 파이프가 오려면, 좌측 칸에서 좌측, 좌측대각선으로부터 오는 파이프의 경우의 수를 고려한다.

  2. 해당 위치에 좌측대각선에서 파이프가 오려면, 좌측대각선 칸에서 세 방향 모두의 파이프의 경우의 수를 고려한다.

  3. 해당 위치에 위쪽에서 파이프가 오려면, 위쪽 칸에서 좌측대각선, 위측으로부터 오는 파이프의 경우의 수를 고려한다.

  따라서 점화식은 아래와 같이 세울 수 있다.

 

  1. dp[ i ][ j ][Left] = dp[ i ][ j - 1 ][LEFT] + dp[ i ][ j - 1 ][DIA];

  2. dp[ i ][ j ][DIA] = dp[ i - 1 ][ j - 1 ][LEFT] +  dp[ i - 1 ][ j - 1 ][ UP] + dp[ i - 1 ][ j - 1 ][DIA];

  3. dp[ i ][ j ][UP] = dp[ i - 1 ][ j ][DIA] + dp[ i - 1 ][ j ][ UP];

 

 

  이 때 대해서 그 위치가 벽이면 체크 할 필요가 없고, 현재 위치에 대각선 파이프를 두는 경우를 고려한다면, 현재 위치에서 위쪽과 좌측에 벽이 있는 경우를 고려해야 한다.

 

  진한 초록색 부분이 현재 좌표이며, 연한 연두색 부분은 그 경우 고려하는 좌표이다. 회색 파이프는 현재 경우의 수를 계산중인 파이프, 노란색 파이프들은 각 상황마다의 회색 파이프를 두는 경우 고려해야하는 파이프들이다. 또한 좌측 대각선 파이프를 두는 경우엔 사진처럼 좌측과 위쪽에 벽이 없는 경우에 경우의 수를 따져야 한다.

---

  Code 

#include <iostream>
#include <vector>

using namespace std;
typedef pair<int, int> pii;

enum board { ground = 0, wall };
enum status { EMPTY = 0, LEFT, UP, DIA };

vector<vector<short>> map;
vector<vector<vector<int>>> dp; // dp[i][j][k] == i, j 에서 k dir 의 값
int n;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	map.assign(n + 1, vector<short>(n + 1, 0));
	dp.assign(n + 1, vector<vector<int>>(n + 1, vector<int>(4, 0)));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j <= n; j++) {
			if (i == 1) {
				if (map[i][j] == ground) dp[i][j][LEFT] = 1;
				else if (map[i][j] == wall) break; // 더이상 첫 번째 행엔 파이프 못 놓음
			}
			else {
				if (map[i][j] == wall) continue;

				dp[i][j][LEFT] = dp[i][j - 1][LEFT] + dp[i][j - 1][DIA];
				dp[i][j][UP]   = dp[i - 1][j][DIA]  + dp[i - 1][j][UP];

				if (map[i - 1][j - 1] == ground && map[i - 1][j] == ground && map[i][j - 1] == ground)
					dp[i][j][DIA] = dp[i - 1][j - 1][LEFT] + dp[i - 1][j - 1][UP] + dp[i - 1][j - 1][DIA];
			}
		}
	}

	cout << dp[n][n][LEFT] + dp[n][n][DIA] + dp[n][n][UP];
}