[백준/BOJ] 백준 17070번 : 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

파이프가 어떤 모습(가로방향, 세로방향, 대각선 방향)인지에 따라 움직일 수 있는 방향이 다르므로, 파이프가 어떤 모습으로 있는지에 따라 파이프를 옮기며 목적지(오른쪽 아래 부분)에 도달하는 개수를 센다

 

코드

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

int n;
int board[16][16];
int cache[16][16][16][16];

//cache초기화
void makeCache()
{
	for (int i = 0; i < 16; i++)
		for (int j = 0; j < 16; j++)
			for (int k = 0; k < 16; k++)
				for (int l = 0; l < 16; l++)
					cache[i][j][k][l] = -1;
}

//파이프가 pipe위치에 있을때 파이프를 목적지(오른쪽 아래 부분)로 이동시키는 방법의 개수
int Solve(pair<pair<int, int>, pair<int, int>> pipe)
{
	//기저사례 (파이프가 목적지 도달했을때)
	if (pipe.second.first == n - 1 && pipe.second.second == n - 1)
		return 1;

	int& ret = cache[pipe.first.first][pipe.first.second][pipe.second.first][pipe.second.second];
	
	//계산한적이 있을때
	if (ret != -1)
		return ret;

	ret = 0;

	pair<pair<int, int>, pair<int, int>> moved_pipe;
	
	//파이프가 가로 방향일때
	if (pipe.first.first == pipe.second.first && pipe.first.second+1 == pipe.second.second)
	{
		//가로 이동
		if (pipe.second.second + 1 < n && board[pipe.second.first][pipe.second.second + 1] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first, pipe.second.second + 1));
			ret += Solve(moved_pipe);
		}

		//대각선 이동
		if (pipe.second.first + 1 < n && pipe.second.second + 1 < n && board[pipe.second.first][pipe.second.second + 1] != 1 && board[pipe.second.first + 1][pipe.second.second + 1] != 1 && board[pipe.second.first + 1][pipe.second.second] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first + 1, pipe.second.second + 1));
			ret += Solve(moved_pipe);
		}
	}

	//파이프가 세로 방향일때
	if (pipe.first.second == pipe.second.second && pipe.first.first + 1 == pipe.second.first)
	{
		//세로 이동
		if (pipe.second.first + 1 < n && board[pipe.second.first + 1][pipe.second.second] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first + 1, pipe.second.second));
			ret += Solve(moved_pipe);
		}
		//대각선 이동
		if (pipe.second.first + 1 < n && pipe.second.second + 1 < n && board[pipe.second.first][pipe.second.second + 1] != 1 && board[pipe.second.first + 1][pipe.second.second + 1] != 1 && board[pipe.second.first + 1][pipe.second.second] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first + 1, pipe.second.second + 1));
			ret += Solve(moved_pipe);
		}
	}
	//파이프가 대각선 방향일때
	if (pipe.first.first + 1 == pipe.second.first && pipe.first.second + 1 == pipe.second.second)
	{
		//가로 이동
		if (pipe.second.second + 1 < n && board[pipe.second.first][pipe.second.second + 1] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first, pipe.second.second + 1));
			ret += Solve(moved_pipe);
		}

		//세로 이동
		if (pipe.second.first + 1 < n && board[pipe.second.first + 1][pipe.second.second] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first + 1, pipe.second.second));
			ret += Solve(moved_pipe);
		}

		//대각선 이동
		if (pipe.second.first + 1 < n && pipe.second.second + 1 < n && board[pipe.second.first][pipe.second.second + 1] != 1 && board[pipe.second.first + 1][pipe.second.second + 1] != 1 && board[pipe.second.first + 1][pipe.second.second] != 1)
		{
			moved_pipe = make_pair(make_pair(pipe.second.first, pipe.second.second), make_pair(pipe.second.first + 1, pipe.second.second + 1));
			ret += Solve(moved_pipe);
		}

	}

	return ret;
}

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

	int temp;
	pair<pair<int, int>,pair<int,int>> pipe;

	makeCache();

	cin >> n;

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

	//처음 파이프는 (0,0),(0,1) 위치에 놓는다
	pipe = make_pair(make_pair(0, 0),make_pair(0,1));

	cout << Solve(pipe);

	return 0;
}