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

17070번: 파이프 옮기기 1

1. 가로

2. 세로

3. 대각선

 

현재 위치는 항상 0번이고

가로일 땐 1, 3번

세로일 땐 2, 3번

대각선일 땐 1, 2, 3번으로 이동할 수 있다.

 

이 패턴을 이용해

이전에 어느 방향이었는지와 현재 위치를 넘겨주며

재귀 호출로 완전 탐색을 구현하면 된다.

#include <iostream>
using namespace std;
int N, d, res;
int arr[17][17], dx[3] = { 0, 1, 1 }, dy[3] = { 1, 0, 1 };
bool isHorizontal(int x, int y) {
	x += dx[0], y += dy[0];
	if (x >= 0 && x < N && y >= 0 && y < N && !arr[x][y]) return true;
	else return false;
}
bool isVertical(int x, int y) {
	x += dx[1], y += dy[1];
	if (x >= 0 && x < N && y >= 0 && y < N && !arr[x][y]) return true;
	else return false;
}
bool isDiagonal(int x, int y) {
	for (int i = 0; i < 3; i++) {
		if (x + dx[i] >= 0 && x + dx[i] < N && y + dy[i] >= 0 && y + dy[i] < N && !arr[x + dx[i]][y + dy[i]]) continue;
		else return false;
	}
	return true;
}
void Move(int x, int y, int d) {
	if (x == N - 1 && y == N - 1) {
		res++;
		return;
	}
	switch (d)
	{
	case 0:
		if (isHorizontal(x, y)) Move(x + dx[0], y + dy[0], 0);
		if (isDiagonal(x, y)) Move(x + dx[2], y + dy[2], 2);
		break;
	case 1:
		if (isVertical(x, y)) Move(x + dx[1], y + dy[1], 1);
		if (isDiagonal(x, y)) Move(x + dx[2], y + dy[2], 2);
		break;
	case 2:
		if (isHorizontal(x, y)) Move(x + dx[0], y + dy[0], 0);
		if (isVertical(x, y)) Move(x + dx[1], y + dy[1], 1);
		if (isDiagonal(x, y)) Move(x + dx[2], y + dy[2], 2);
		break;
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> arr[i][j];
	Move(0, 1, 0);
	cout << res;
	return 0;
}