BOJ : 17069 파이프 옮기기 2

---

[BOJ 17069(G5)리뷰]

오랜만에 푼 DP문제다. 오랜만에 DP풀려니까 역시 힘들었다.

이 문제는 예전에 풀려고하다 도중에 포기했던 문제지만, 이번엔 한번에 풀어서 기분이 좋다.

코드를 보면 알겠지만 문제에 주어진 조건을 그대로 구현하여 재귀함수로 처리하면 된다. 나는 미리 맵의 벽을 그린다음에 이동할 수 있는지 없는지 확인하고 이동이 가능하면 다음 함수를 실행하도록 했다.

맵의 최대크기가 엄청 크기에 dp를 사용하지 않으면 시간초과가 난다. 가고자 하는 경로가 이미 목적지에 도착한적이 있던 경로라면 굳이 가지 않고서도 도착할 수 있음을 알수있다. 이를 이용하여 실행시간을 단축해야 한다.

/*
	21.01.05
	BOJ : 17069 파이프 옮기기 2 (https://www.acmicpc.net/problem/17069)
	동적계획법
*/
#include <bits/stdc++.h>
using namespace std;

int board[35][35];
long long int dp[35][35][3];
int N;

long long int go(int r, int c, int dir) {
	if (r == N && c == N) {
		return 1;
	}
	if (dp[r][c][dir]) {
		return dp[r][c][dir];
	}

	dp[r][c][dir] = 0;
	switch (dir) {
	case 0:
	{
		if (board[r][c + 1] == 0) {
			dp[r][c][dir] += go(r, c + 1, 0);
		}

		if (board[r][c + 1] == 0 && board[r + 1][c + 1] == 0 && board[r + 1][c] == 0) {
			dp[r][c][dir] += go(r + 1, c + 1, 1);
		}

		break;
	}
	case 1: {
		if (board[r][c + 1] == 0) {
			dp[r][c][dir] += go(r, c + 1, 0);
		}
		if (board[r][c + 1] == 0 && board[r + 1][c + 1] == 0 && board[r + 1][c] == 0) {
			dp[r][c][dir] += go(r + 1, c + 1, 1);
		}
		if (board[r + 1][c] == 0) {
			dp[r][c][dir] += go(r + 1, c, 2);
		}
		break;
	}
	case 2: {
		if (board[r][c + 1] == 0 && board[r + 1][c + 1] == 0 && board[r + 1][c] == 0) {
			dp[r][c][dir] += go(r + 1, c + 1, 1);
		}

		if (board[r + 1][c] == 0) {
			dp[r][c][dir] += go(r + 1, c, 2);
		}

		break;
	}
	}

	return dp[r][c][dir];
}

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

	

	cin >> N;
	for (int i = 0; i <= N + 1; i++) {
		for (int j = 0; j <= N + 1; j++) {
			if (i == 0 || j == 0 || i > N || j > N) {
				board[i][j] = 1;
			}
			else
				cin >> board[i][j];
		}
	}

	cout << go(1, 2, 0);

}