파이프 옮기기 1

문제

• 백준 17070번 - 파이프 옮기기 1

언어

• JavaScript

순서도

1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
2. dp 배열의 base 값 정의
3. 점화식과 base 값을 이용해서 dp 배열 채우기

문제 풀이 step 1

• 집의 크기는 N x N 의 격자판이며, 1 x 1 크기의 정사각형 칸으로 나누어져 있습니다.
• 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r 은 행의 번호, c 는 열의 번호이고, 행과 열의 번호는 1 부터 시작합니다.
• 각각의 칸은 빈 칸이거나 벽입니다. 집 수리를 위해서 파이프 하나를 옮기려고 합니다.
• 파이프는 2 개의 연속된 칸을 차지하는 크기이며, 회전시킬 수 있고, 3 가지 방향이 가능합니다.
• 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 합니다.
• 벽에는 새로운 벽지를 발랐기 때문에 파이프가 벽을 긁으면 안됩니다. 즉, 파이프는 항상 빈 칸만 차지해야 합니다.
• 파이프를 밀 수 있는 방향은 총 3 가지 (오른쪽, 아래, 오른쪽 아래 대각선) 입니다.
• 파이프는 밀면서 회전시킬 수 있습니다. 회전은 45도만 가능하며 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향입니다.

문제 풀이 step 2

• 위의 정보를 바탕으로 집에서 파이프를 N x N 위치로 옮기는 방법의 수를 구하는 문제입니다.
• DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
• dp[r][c][0] = (1, 1) 부터 (r, c) 까지 가로 모양으로 파이프를 옮기는 방법의 수
• dp[r][c][1] = (1, 1) 부터 (r, c) 까지 세로 모양으로 파이프를 옮기는 방법의 수
• dp[r][c][2] = (1, 1) 부터 (r, c) 까지 대각선 모양으로 파이프를 옮기는 방법의 수
• 점화식은 파이프에 모양에 따라 3 가지로 나뉩니다.
  • dp[r][c][0] = dp[r][c - 1][0] + dp[r][c - 1][2]
    • 가로 모양에서 오른쪽 방향으로 미는 경우
    • 대각선 모양에서 회전해서 오른쪽 방향으로 미는 경우
  • dp[r][c][1] = dp[r - 1][c][1] + dp[r - 1][c][2]
    • 세로 모양에서 아래 방향으로 미는 경우
    • 대각선 모양에서 회전해서 아래 방향으로 미는 경우
  • dp[r][c][2] = dp[r - 1][c - 1][0] + dp[r - 1][c - 1][1] + dp[r - 1][c - 1][2]
    • 가로 모양에서 회전해서 대각선 방향으로 미는 경우
    • 세로 모양에서 회전해서 대각선 방향으로 미는 경우
    • 대각선 모양에서 대각선 방향으로 미는 경우
    • 단, 이 경우 벽에 닿으면 안 됩니다.
• 위와 같이 점화식을 구하고 base 값을 설정한 다음에 bottom-up 방식으로 dp 배열을 채운 후에 “dp[n][n][0] + dp[n][n][1] + dp[n][n][2]” 값을 출력하면 정답입니다.
• 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const home = input.slice(1).map((v) => v.split(" ").map(Number));

	// 0: 가로, 1: 세로, 2: 대각선
	// [[[가로, 세로, 대각선], [가로, 세로, 대각선], ...]]
	const dp = Array.from({length: n}, () =>
		Array.from({length: n}, () => Array(n).fill(0))
	);

	// base
	dp[0][1][0] = 1;
	// base - 0 행 채우기
	for (let j = 2; j < n; j++) {
		// 벽이면 파이프 이동 불가
		if (home[0][j] === 1) continue;
		dp[0][j][0] = dp[0][j - 1][0];
	}
	// base - 1 행 채우기
	for (let j = 2; j < n; j++) {
		// 벽이면 파이프 이동 불가
		if (home[1][j] === 1) continue;
		dp[1][j][0] = dp[1][j - 1][0] + dp[1][j - 1][2];
		dp[1][j][1] = dp[0][j][1] + dp[0][j][2];

		// 대각선 이동시 벽에 닿으면 이동 불가
		if (home[0][j] === 1 || home[1][j - 1] === 1) continue;
		dp[1][j][2] = dp[0][j - 1][0] + dp[0][j - 1][1] + dp[0][j - 1][2];
	}

	// bottom-up
	for (let i = 1; i < n; i++) {
		for (let j = 2; j < n; j++) {
			// 벽이면 파이프를 이동 불가
			if (home[i][j] === 1) continue;
			dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];
			dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];

			// 대각선 이동시 벽에 닿으면 이동 불가
			if (home[i - 1][j] === 1 || home[i][j - 1] === 1) continue;
			dp[i][j][2] =
				dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
		}
	}

	// n - 1 x n - 1 까지 파이프를 옮기는 방법의 수 출력
	return dp[n - 1][n - 1].reduce((ac, v) => ac + v);
};

console.log(solution(input));