골드5 - 백준 17069 파이프 옮기기 2

백준 17069 파이프 옮기기 2

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

접근방법

일반적인 BFS로 풀면 경우의 수가 너무 많아 시간초과가 나기 때문에 DFS를 이용한 백트래킹으로 경우의 수를 DP에 저장하여 동적 프로그래밍으로 문제를 해결하였다.

풀이

우선 dp배열의 도착지점 위치를 파이프 3개의 경우 모두 1로 초기화를 해주었다. 그리고 처음 파이프의 상태에서 벽을 고려하고 파이프의 상태를 고려하여 움직일 수 있는 파이프의 경우를 재귀적으로 계속 진행해주었다. 파이프의 상태가 3개로 나뉘기 때문에 dp배열도 3개의 상태로 구분하여 값을 저장하였고 dp배열에 경우의 수 값이 저장되어 있다면 바로 sum에 더해주고 -1이라면 계속 재귀를 진행하는 식으로 경우의 수를 전부 구해주어 출력해주었다.

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

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

// 0:가로, 1:대각선 2:세로
long long dfs(int x, int y, int type)
{
	long long sum = 0;
	// 가로
	if (type == 0)
	{
		// 가로
		if (x >= 0 && x < N && y + 1 >= 0 && y + 1 < N)
		{
			if (board[x][y + 1] != 1)
			{
				if (dp[x][y + 1][0] != -1)
					sum += dp[x][y + 1][0];
				else
					sum += dfs(x, y + 1, 0);
			}
		}

		// 대각
		if (x + 1 >= 0 && x + 1 < N && y + 1 >= 0 && y + 1 < N)
		{
			if (board[x][y + 1] != 1 && board[x + 1][y + 1] != 1 && board[x + 1][y] != 1)
			{
				if (dp[x + 1][y + 1][1] != -1)
					sum += dp[x + 1][y + 1][1];
				else
					sum += dfs(x + 1, y + 1, 1);
			}
		}
	}
	// 대각선
	else if (type == 1)
	{
		// 가로
		if (x >= 0 && x < N && y + 1 >= 0 && y + 1 < N)
		{
			if (board[x][y + 1] != 1)
			{
				if (dp[x][y + 1][0] != -1)
					sum += dp[x][y + 1][0];
				else
					sum += dfs(x, y + 1, 0);
			}
		}

		// 대각
		if (x + 1 >= 0 && x + 1 < N && y + 1 >= 0 && y + 1 < N)
		{
			if (board[x][y + 1] != 1 && board[x + 1][y + 1] != 1 && board[x + 1][y] != 1)
			{
				if (dp[x + 1][y + 1][1] != -1)
					sum += dp[x + 1][y + 1][1];
				else
					sum += dfs(x + 1, y + 1, 1);
			}
		}

		// 세로
		if (x + 1 >= 0 && x + 1 < N && y >= 0 && y < N)
		{
			if (board[x + 1][y] != 1)
			{
				if (dp[x + 1][y][2] != -1)
					sum += dp[x + 1][y][2];
				else
					sum += dfs(x + 1, y, 2);
			}
		}
	}
	// 세로
	else
	{
		// 대각
		if (x + 1 >= 0 && x + 1 < N && y + 1 >= 0 && y + 1 < N)
		{
			if (board[x][y + 1] != 1 && board[x + 1][y + 1] != 1 && board[x + 1][y] != 1)
			{
				if (dp[x + 1][y + 1][1] != -1)
					sum += dp[x + 1][y + 1][1];
				else
					sum += dfs(x + 1, y + 1, 1);
			}
		}

		// 세로
		if (x + 1 >= 0 && x + 1 < N && y >= 0 && y < N)
		{
			if (board[x + 1][y] != 1)
			{
				if (dp[x + 1][y][2] != -1)
					sum += dp[x + 1][y][2];
				else
					sum += dfs(x + 1, y, 2);
			}
		}
	}

	return dp[x][y][type] = sum;
}

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

	memset(dp, -1, sizeof(dp));
	cin >> N;

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

	dp[N - 1][N - 1][0] = 1;
	dp[N - 1][N - 1][1] = 1;
	dp[N - 1][N - 1][2] = 1;

	dfs(0, 1, 0);

	cout << dp[0][1][0] << endl;
	return 0;
}