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

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다.

 

입력 배열의 최대 크기가 16 x 16으로 작긴 하다. 그러나 혹시 모를 시간 초과를 대비하여 다이나믹 프로그래밍으로 확실하게 시간을 줄였다.

 

dp[y][x][direction] : (y, x) 위치에서 direction으로 파이프가 놓여져 있을 때 이동시킬 수 있는 경우의 수

로 놓아서 문제를 쉽게 해결할 수 있었다.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

#define MAX 16
#define GARO 0
#define DAEGAK 1
#define SERO 2

int N;
int house[MAX + 1][MAX + 1];
int dp[MAX + 1][MAX + 1][3];

void init() {
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			for (int i = 0; i < 3; i++) {
				dp[y][x][i] = -1;
			}
		}
	}
}

void input() {
	cin >> N;
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			cin >> house[y][x];
		}
	}
}

bool inRange(int y, int x) {
	if (1 <= y && y <= N && 1 <= x && x <= N) {
		return true;
	}
	return false;
}

int solve(int y, int x, int direction) {
	if (y == N && x == N) {
		return 1;
	}
	if (dp[y][x][direction] != -1) {
		return dp[y][x][direction];
	}
	int result = 0;
	if (direction == GARO) {
		// garo
		if (inRange(y, x + 1) && house[y][x + 1] == 0) {
			result += solve(y, x + 1, GARO);
		}
		// daegak
		if (inRange(y, x + 1) && inRange(y + 1, x + 1) && inRange(y + 1, x)) {
			if (house[y][x + 1] == 0 && house[y + 1][x + 1] == 0 && house[y + 1][x] == 0) {
				result += solve(y + 1, x + 1, DAEGAK);
			}
		}
		return dp[y][x][direction] = result;
	} else if (direction == SERO) {
		// sero
		if (inRange(y + 1, x) && house[y + 1][x] == 0) {
			result += solve(y + 1, x, SERO);
		}
		// daegak
		if (inRange(y, x + 1) && inRange(y + 1, x + 1) && inRange(y + 1, x)) {
			if (house[y][x + 1] == 0 && house[y + 1][x + 1] == 0 && house[y + 1][x] == 0) {
				result += solve(y + 1, x + 1, DAEGAK);
			}
		}
		return dp[y][x][direction] = result;
	} else {
		// garo
		if (inRange(y, x + 1) && house[y][x + 1] == 0) {
			result += solve(y, x + 1, GARO);
		}
		// daegak
		if (inRange(y, x + 1) && inRange(y + 1, x + 1) && inRange(y + 1, x)) {
			if (house[y][x + 1] == 0 && house[y + 1][x + 1] == 0 && house[y + 1][x] == 0) {
				result += solve(y + 1, x + 1, DAEGAK);
			}
		}
		// sero
		if (inRange(y + 1, x) && house[y + 1][x] == 0) {
			result += solve(y + 1, x, SERO);
		}
		return dp[y][x][direction] = result;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	input();
	init();
	cout << solve(1, 2, GARO) << '\n';

	return 0;
}