백준 17070 C++ - 파이프 옮기기 1

Intro

문제해결 및 소스코드

문제의 조건을 먼저 살펴보자.

파이프는 한번움직일 때 45도 만큼만 움직일 수 있다. 즉, 다음과 같다.

1. 파이프가 가로로 놓인상태일 때
   • 가로로 움직인다.
   • 오른쪽 대각선아래로 움직인다.
2. 파이프가 세로로 놓인상태일 때
   • 세로로 움직인다.
   • 오른쪽 대각선아래로 움직인다.
3. 파이프가 대각선으로 놓은상태일 때
   • 가로로 움직인다.
   • 세로로 움직인다.
   • 오른쪽 대각선아래로 움직인다.

파이프가 어떤 상태로 놓여있던간에 오른쪽 대각선아래로는 움직일 수 있다는 공통점을 발견할 수 있다.

나는 문제를 해결하기위해 DP 방식으로 접근해보았다.

특정 좌표(x,y)에 파이프가 놓일 수 있는 방법은 (가로, 세로, 대각선) 3가지이다.

위 그림에서 (3,3)에 파이프가 놓이는 방법을 생각해보자.

1. (3,3)에서 파이프가 가로로 놓일 때
2. (3,3)에서 파이프가 세로로 놓일 때
3. (3,3)에서 파이프가 대각선으로 놓일 때

먼저, 파이프가 가로로놓이려면 2가지 방법이있다.

(2,3)에서 파이프가 가로로 놓여있을 때 또는 대각선으로 놓여있을 때만 (3,3)에서 가로로 놓여질 수 있다.

세로, 대각선으로 놓이려고 할때도 마찬가지이다.

따라서 다음과 같은 식을 도출해낼 수 있다.

// dp[x][y] : (x,y)에 파이프가 놓이는 방법의 갯수
int dp[17][17][3];// dp[x][y][0] - (x,y)에서 파이프가 가로로 놓이는 방법수, [1] - 세로로 놓이는 방법수, [2] - 대각선으로 놓이는 방법수

dp[row][col][0] = dp[row][col - 1][0] + dp[row][col - 1][2];		// (row,col)에 가로로 놓일수 있는 방법
dp[row][col][1] = dp[row - 1][col][1] + dp[row - 1][col][2];		// (row,col)에 세로로 놓일수 있는 방법
// (row,col)에 대각선으로 놓일 수 있는 방법
dp[row][col][2] = dp[row - 1][col - 1][0] + dp[row - 1][col - 1][1] + dp[row - 1][col - 1][2]; 

그 다음 조건을 생각해보자.

집에는 빈곳만있는것이 아닌, 벽도있다. 파이프는 벽을 통과할 수 없다.

또한 주의해야할점은 대각선으로 옮기려할때다.

(x,y)에 벽이있다면 당연히 파이프를 놓을 방법이없지만 (x,y)에 벽이 없다고해도 만약 (x,y)와 인접한 (x-1,y), (x,y-1)에 벽이 존재한다면

(x,y)에는 대각선으로 파이프를 놓을수없게된다.

이 조건을 추가하여 전체 코드를 작성하였다.

#include <iostream>

using namespace std;

int map[17][17];		// 집

// dp[x][y] : (x,y)에 파이프가 놓이는 방법의 갯수
int dp[17][17][3];		// dp[x][y][0] - (x,y)에서 파이프가 가로로 놓이는 방법수, [1] - 세로로 놓이는 방법수, [2] - 대각선으로 놓이는 방법수

int main()
{
	int n;				// 집 크기
	cin >> n;

	// 집 상태 입력(0:빈칸, 1:벽)
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= n;j++)
		{
			cin >> map[i][j];
		}
	}

	// 초기값
	dp[1][2][0] = 1;

	for (int col = 2;col <= n;col++)
	{
		if (map[0][col] != 1)
			dp[0][col][0] = dp[0][col - 1][0];
	}
	// 
	for (int row = 1; row <= n;row++)
	{
		for (int col = 3; col <= n; col++)
		{
			// 벽이 아닐 때만
			if (map[row][col] != 1)
			{
				dp[row][col][0] = dp[row][col - 1][0] + dp[row][col - 1][2];		// (row,col)에 가로로 놓일수 있는 방법
				dp[row][col][1] = dp[row - 1][col][1] + dp[row - 1][col][2];		// (row,col)에 세로로 놓일수 있는 방법
				if (map[row - 1][col] != 1 && map[row][col - 1] != 1)
				{
					// (row,col)에 대각선으로 놓일 수 있는 방법
					dp[row][col][2] = dp[row - 1][col - 1][0] + dp[row - 1][col - 1][1] + dp[row - 1][col - 1][2]; 
				}
			}
			
		}
	}

	cout << dp[n][n][0] + dp[n][n][1] + dp[n][n][2];
}