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

백준 17070

dfs로 풀려고 했는데 DP로도 풀 수 있을 것 같아서 DP로 풀어보았다.
DP가 더 빠르지만 dfs로도 풀리는 듯!

int N;
bool map[16][16];	// true=벽, false=빈칸
int ans[16][16][3];	// 파이프 방향에 따른 방법의 수

예를 들어 파이프의 오른쪽 끝이 (2, 2)에 도착했을 때 파이프의 방향이 가로일 경우의 방법의 수는 ans[2][2][0]이다.

파이프를 45도까지만 회전할 수 있으므로

1. 파이프 끝이 (i, j)에 가로 방향으로 도착하는 방법의 수
   = 파이프 끝이 (i, j-1)에 가로 방향으로 도착하는 방법의 수 + 대각선 방향으로 도착하는 방법의 수

2. 파이프 끝이 (i, j)에 대각선 방향으로 도착하는 방법의 수
   = 파이프 끝이 (i-1, j-1)에 도착하는 방법의 수

3. 파이프 끝이 (i, j)에 세로 방향으로 도착하는 방법의 수
   = 파이프 끝이 (i-1, j)에 대각선 방향으로 도착하는 방법의 수 + 세로 방향으로 도착하는 방법의 수

이를 코드로 나타내면

ans[i][j][0] = ans[i][j - 1][0] + ans[i][j - 1][1];
ans[i][j][1] = ans[i - 1][j - 1][0] + ans[i - 1][j - 1][1] + ans[i - 1][j - 1][2]
ans[i][j][2] = ans[i - 1][j][1] + ans[i - 1][j][2];

이때 (i, j)가 벽이라면 파이프가 (i, j)에 도착할 수 있는 방법이 없기 때문에 (i, j)가 빈칸인 경우에만 수행한다.

if (!map[i][j])	// (i, j)가 빈칸이면
{
	ans[i][j][0] = ans[i][j - 1][0] + ans[i][j - 1][1];
    ans[i][j][1] = ans[i - 1][j - 1][0] + ans[i - 1][j - 1][1] + ans[i - 1][j - 1][2]
	ans[i][j][2] = ans[i - 1][j][1] + ans[i - 1][j][2];
}

파이프를 가로나 세로로 미는 경우는 상관 없지만
파이프를 대각선으로 미는 경우에는 (i, j)뿐만 아니라 (i-1, j), (i, j-1)도 빈칸이어야 하므로 이를 체크해야 한다.

if (!map[i][j])	// (i, j)가 빈칸이면
{
	ans[i][j][0] = ans[i][j - 1][0] + ans[i][j - 1][1];
	ans[i][j][2] = ans[i - 1][j][1] + ans[i - 1][j][2];
	if (!map[i-1][j] && !map[i][j-1])	// (i-1, j), (i, j-1)가 빈칸
    	ans[i][j][1] = ans[i - 1][j - 1][0] + ans[i - 1][j - 1][1] + ans[i - 1][j - 1][2]
}

그런데 모든 칸마다 이 코드를 수행하면 매번 (i-1, j)와 (i, j-1)이 범위 내인지 체크해야 한다. 따라서 어차피 고정인 0열, 1열은 제외하고, 0행은 먼저 체크한 이후 위의 코드는 (1, 2)부터 수행한다.

for (int i = 1; i < N; i++)	// 1행부터
	{
		for (int j = 2; j < N; j++)	// 2열부터
		{
			if (!map[i][j])	// 빈칸이면
			{
				ans[i][j][0] = ans[i][j - 1][0] + ans[i][j - 1][1];
				ans[i][j][2] = ans[i - 1][j][1] + ans[i - 1][j][2];
				if (!map[i-1][j] && !map[i][j-1])
					ans[i][j][1] = ans[i - 1][j - 1][0] + ans[i - 1][j - 1][1] + ans[i - 1][j - 1][2];
			}
		}
	}

가장 처음에 파이프가 (0, 0), (0, 1)에 위치하므로 파이프의 오른쪽 끝이 (0, 1)이다.
=> ans[0][1][0]=1

파이프의 끝이 0행인 경우는 가로 방향인 경우 뿐이다. 이때 j열이 벽이라면 (0, j)이후부터는 파이프가 갈 수 있는 방법이 없다.

ans[0][1][0] = 1;
	for (int j = 2; j < N; j++)	// (0, 2)부터 (0, N-1)까지 체크
		if (!map[0][j])
			ans[0][j][0] = ans[0][j - 1][0];

전체 코드

#include <iostream>
using namespace std;

int N;
bool map[16][16];
int ans[16][16][3];

void solve()
{
	ans[0][1][0] = 1;
	for (int j = 2; j < N; j++)	// (0, 2)부터 (0, N-1)까지 체크
		if (!map[0][j])
			ans[0][j][0] = ans[0][j - 1][0];

	for (int i = 1; i < N; i++)	// 1행부터
	{
		for (int j = 2; j < N; j++)	// 2열부터
		{
			if (!map[i][j])	// 빈칸이면
			{
				ans[i][j][0] = ans[i][j - 1][0] + ans[i][j - 1][1];
				ans[i][j][2] = ans[i - 1][j][1] + ans[i - 1][j][2];
				if (!map[i-1][j] && !map[i][j-1])
					ans[i][j][1] = ans[i - 1][j - 1][0] + ans[i - 1][j - 1][1] + ans[i - 1][j - 1][2];
			}
		}
	}
}


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

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

	solve();

	cout << ans[N - 1][N - 1][0] + ans[N - 1][N - 1][1] + ans[N - 1][N - 1][2];
}