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

파이프를 이동할 수 있는 경우의 수를 구하는 문제이다.

파이프 크기는 2X1이고, 오른쪽으로만 이동할 수 있으며, 가로, 세로, 대각선 방향으로만 이동할 수 있다.

 

2칸을 차지하긴 하지만 결국 끝점이 목적지에만 있으면 되기 때문에 끝점만 보면 된다.

보자마자 bfs dfs가 생각나서 dfs를 시도했다.

한번에 45도밖에 회전을 못하기 때문에 곧바로 "가로->세로, 세로->가로"로 이동할 수 없음을 주의하자.

(반드시 대각선 선 상태를 거쳐야 함. 이거땜에 삽질....)

dfs를 돌 때 현재 파이프 상태가 가로인지, 세로 또는 대각선인지 매번 저장해주고, 각 파이프 상태에 따라 이동이 가능한지를 벽의 유무를 통해 확인한다.

 

1. 가로/세로 상태일 때는 다음 정점(house[nx][ny])에 벽이 있는지 확인

2. 대각선 상태일 때는 오른쪽과 아래 정점(house[x+1][y], house[x][y+1])에 벽이 있는지 확인

 

// 17070_파이프_옮기기1.cpp
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <iostream>
#define MAX 16

int n; // 집의 크기
int house[MAX][MAX] = { 0, };

int dir[3][2] = { {0, 1}, {1, 0}, {1, 1} }; // 가로, 세로, 대각선
int answer = 0; // 경우의 수

// x, y는 파이프의 끝부분 좌표를 나타냄
void dfs(int x, int y, int pipe) { // pipe: 가로(0), 세로(1), 대각선(2)
	if (x == n - 1 && y == n - 1) { 
		answer++;
		return;
	}

	for (int i = 0; i < 3; i++) {
		// 회전은 한번에 45도만 가능
		// 가로 -> 세로, 세로 -> 가로 불가능
		if ((i == 0 && pipe == 1) || (i == 1 && pipe == 0)) continue;

		/* 대각선으로 미는 경우 벽이 있는지 확인 */
		if (i == 2 && (house[x + 1][y] == 1 || house[x][y + 1] == 1)) continue;

		int nx = x + dir[i][0];
		int ny = y + dir[i][1];

		/* 범위를 벗어나거나 벽이면 continue */
		if (nx > n - 1 || ny > n - 1) continue;
		if (house[nx][ny] == 1) continue;

		dfs(nx, ny, i);
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &house[i][j]);
		}
	}

	dfs(0, 1, 0); // 초기 파이프의 끝점 (1, 2), 가로방향
	printf("%d\n", answer);

	return 0;
}