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

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

2) 설명

길이 2의 파이프가 있다.

파이프는 가로, 세로, 대각선(좌상단 -> 우하단) 방향으로 밀 수 있다.

처음에 (1, 1), (1, 2)에 놓여진 파이프를 (N, M)까지 미는 경우의 수를 구하면 된다.

단 파이프는 오른쪽, 아래쪽, 대각선으로만 밀 수 있고, 직각으로는(가로 -> 세로, 세로->가로) 밀 수 없다.

또한 파이프의 이동 경로는 반드시 빈 칸이어야 하고, 대각선의 경우에는 파이프가 놓여져 있는 총 4칸이 빈 칸이어야 한다.

2. 풀이

1) 알고리즘

    : DP

 

2) 풀이 설명

3차원 DP 벡터를 사용했다.

예를 들어 dp[x][y][z]는 x 방식(0 : 가로, 1 : 세로, 2 : 대각선)으로 (y, z)에 도달하는 경우의 수를 나타낸다.

2차원 DP를 사용하지 않고 이동 방식까지 나누어 3차 DP를 사용한 이유는 이동 방식(가로, 세로, 대각선)에 따라 다음에 이동할 수 있는 방식이 달라지기 때문이다.

 

모든 dp를 0으로 초기화해주고 가로 방식의 첫 행만 1로 초기화해주었다.

 

(i, j)로 이동하는 경우의 수는 다음과 같다.

1. (i, j-1)에서 가로 이동 (단 (i, j-1)에서는 세로로 도달했으면 안 된다.)

2. (i-1, j)에서 세로 이동 (단 (i-1, j)에서는 가로로 도달했으면 안 된다.)

3. (i-1, j-1)에서 대각선 이동

 

그러므로 점화식은 다음과 같이 세워진다.

dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1]

dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j]

dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] (단 좌하단, 우상단이 빈 공간일 때)

 

이렇게 다 돌고나면

dp[0][N][M] // 마지막에 가로 방식으로 (N, M)에 도달하는 경우의 수

+ dp[0][N][M] // 마지막에 세로 방식으로 (N, M)에 도달하는 경우의 수

+ dp[0][N][M] // 마지막에 대각선 방식으로 (N, M)에 도달하는 경우의 수

 

이 답이 된다.

 

3. 코드

 

/*
	파이프 옮기기 1
	알고리즘
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N, answer = 0;
	cin >> N;

	vector<vector<int>> house(N+1, vector<int>(N+1));
	/*
		0 - 가로
		1 - 세로
		2 - 대각선
	*/
	vector<vector<vector<int>>> dp(3,vector<vector<int>>(N+1, vector<int>(N+1, 0)));

	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			cin >> house[i][j];

	for(int i=2;i<=N && !house[1][i];i++)
		dp[0][1][i] = 1;

	for(int i=2;i<=N;i++){
		for(int j=2;j<=N;j++){
			if(!house[i][j]){
				dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1];
				dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j];
				if(!house[i-1][j] && !house[i][j-1]){
					dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1];
				}
			}
		}
	}
	for(int i=0;i<3;i++)
		answer += dp[i][N][N];
	
	cout << answer << endl;

	return 0;
}

 

4. 느낀점

 - 초기에 (1, 1), (1, 2)에 파이프가 놓여져있다는 걸 모르고 가로, 세로, 대각선 다 출발했다가 틀렸다. 역시 문제를 잘 읽어야 한다.