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

문제 링크: https://www.acmicpc.net/source/19833442

 

dp, 백트래킹 등등 아무거나 이용해서 풀 수 있습니다.

저는 (n-1, n-1)부터 시작해서 역순으로 (0, 1)까지 가는 dp로 구현했습니다.

여기서 중요한게 dp에 방향까지 저장해줘야 합니다. 직전 파이프가 가로(ㅡ)인 경우 그 다음엔 세로 파이프를 놓을 수 없고, 직전 파이프가 수직(|)인 경우 그 다음엔 가로 파이프를 넣을 수 없으니 이점을 dp에 반영하기 위해 dp배열에 [y][x][dir] 이렇게 방향 차원을 추가해줘야 합니다.

#pragma GCC optimize ("Ofast")

#include <bits/stdc++.h>
using namespace std;

//dir: [0]─ [1]\ [2]|

int n;
bool wall[16][16];
int cache[16][16][3];

constexpr bool in_range(int y, int x) { return y>=0 && y<n && x>=0 && x<n ; }

int solve(int y, int x, int d) {
	if (y == 0 && x == 1 && d == 0) return 1;
	
	auto& ret = cache[y][x][d];
	if (ret != -1) return ret;
	ret = 0;

	if (d == 0 && in_range(y, x-1) && !wall[y][x-1]) {
		ret += solve(y, x-1, 0);
		ret += solve(y, x-1, 1);
	}
	else if (d == 1 && in_range(y-1, x-1) && !wall[y-1][x] && !wall[y][x-1] && !wall[y-1][x-1]) {
		ret += solve(y-1, x-1, 0);
		ret += solve(y-1, x-1, 1);
		ret += solve(y-1, x-1, 2);
	}
	else if (d == 2 && in_range(y-1, x) && !wall[y-1][x]) {
		ret += solve(y-1, x, 1);
		ret += solve(y-1, x, 2);
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	memset(cache, -1, sizeof(cache));
	
	cin >> n;
	for (int i=0; i<n; ++i)
		for (int j=0; j<n; ++j)
			cin >> wall[i][j];

	if (wall[n - 1][n - 1])
		cout << 0 << '\n';
	else
		cout << solve(n - 1, n - 1, 0) + solve(n - 1, n - 1, 1) + solve(n - 1, n - 1, 2) << '\n';

	return 0;
}

dp 안에 식이 좀 대충 적힌거같은데 ;; 아침이라 머리 회전이 안되니 걍 넘어가겠습니다

그냥 (0, 1)부터 시작해서 (n-1, n-1)까지 가는걸로 짜면 더 깔끔할 듯 하네요. 왜 저렇게 짰지?