[BOJ] #17070 _ 파이프 옮기기1

[파이프 옮기기1] https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

조건대로만 파이프 옮기는 것이 가능한 시뮬레이션 문제이다.

dfs를 이용하여 가능한 모든 경우를 찾는 방식으로 구현하였다.

 

[ 소스 코드 ]

 

#include <cstdio>
#include <algorithm>
#define MAX 17

using namespace std;

int dx[] = { 1,0,1 }, dy[] = { 0,1,1 };
int N, result;
int map[MAX][MAX];

void solve(int pipe, int y, int x);
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	map[1][1] = 1;
	map[1][2] = 1;
	solve(0, 1, 2);
	printf("%d\n", result);

	return 0;
}

void solve(int pipe, int y, int x) {
	if (pipe == 0 || pipe == 2) { //가로
		int tmp_y = y + dy[0], tmp_x = x + dx[0];
		if (tmp_y <= N && tmp_x <= N) {
			if (!map[tmp_y][tmp_x]) {
				if (tmp_y == N && tmp_x == N) result++;
				else {
					map[tmp_y][tmp_x] = 1;
					solve(0, tmp_y, tmp_x);
					map[tmp_y][tmp_x] = 0;
				}
			}
		}
	}

	if (pipe == 1 || pipe == 2) { //세로
		int tmp_y = y + dy[1], tmp_x = x + dx[1];
		if (tmp_y <= N && tmp_x <= N) {
			if (!map[tmp_y][tmp_x]) {
				if (tmp_y == N && tmp_x == N) result++;
				else {
					map[tmp_y][tmp_x] = 1;
					solve(1, tmp_y, tmp_x);
					map[tmp_y][tmp_x] = 0;
				}
			}
		}
	}

	int tmp_y = y + dy[2], tmp_x = x + dx[2]; //대각선
	if (tmp_y <= N && tmp_x <= N) {
		if (!map[tmp_y][tmp_x] && !map[y][tmp_x] && !map[tmp_y][x]) {
			if (tmp_y == N && tmp_x == N) result++;
			else {
				map[tmp_y][x] = 1;
				map[y][tmp_x] = 1;
				map[tmp_y][tmp_x] = 1;
				solve(2, tmp_y, tmp_x);
				map[tmp_y][x] = 0;
				map[y][tmp_x] = 0;
				map[tmp_y][tmp_x] = 0;
			}
		}
	}
}