[BOJ-17070] 파이프 옮기기1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

2019년 3월 상시 SW역량 테스트 출제 문제와 유사 문제입니다.

 

이런 유형의 문제를 처음 접해봐서 당시 시험장에서 푸는데 시간이 꽤 걸렸던 것으로 기억합니다.

 

제가 푼 방식의 포인트는 현재 파이프의 상태(가로, 세로, 대각선인지의 여부)와 다음에 놓일 상태를 매개변수로 주냐 안주냐였습니다.

 

이전 정보에 대해서 다음에 놓일 위치가 판단되기 때문입니다.

 

-풀이 방법

1. map 정보를 입력 받는다.

 

2. 초기 상태(0,0), (0,1)에 파이프가 가로로 놓여있는 것을 방문 처리 해주고 dfs 탐색을 시작합니다.

 

3. dfs탐색을 하는 함수의 매개변수로는 이동할 파이프 앞부분의 현재 좌표, 현재 놓일 상태, 전에 놓였던 상태를 줬습니다.

 

4. 매개변수의 값에 따라 다음에 놓일 파이프의 상태를 백트래킹으로 방문처리 해줬고 (n-1,n-1)에 도달할 경우 경로가 완성되기 때문에 결과값을 1 더해줘서 답을 구했습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int n, res;
int map[17][17];
bool visited[17][17];
const int dy[] = { 0,1,1 };
const int dx[] = { 1,1,0 };

//dir == 0 -> 오른쪽, dir == 1 -> 대각선, dir == 2 -> 아래
void dfs(int u, int v, int cur, int before) {
	
	if (u >= n || v >= n) return;

	if (u == n - 1 && v == n - 1) {
		res += 1;
		return;
	}

	if ((before == 0 || before == 1) && cur == 0) {
		if (map[u][v + 1] == 0 && visited[u][v + 1] == 0) {
			visited[u][v + 1] = 1;
			dfs(u, v + 1, 0, cur);
			visited[u][v + 1] = 0;
		}

		if (map[u][v+1] == 0 && map[u + 1][v + 1] == 0 && map[u+1][v] == 0) {
			if (visited[u][v + 1] == 0 && visited[u + 1][v + 1] == 0 && visited[u + 1][v] == 0) {
				visited[u + 1][v + 1] = 1;
				dfs(u + 1, v + 1, 1, cur);
				visited[u + 1][v + 1] = 0;
			}
		}
	}

	else if (cur == 1) {
		if (map[u][v + 1] == 0 && visited[u][v + 1] == 0) {
			visited[u][v + 1] = 1;
			dfs(u, v + 1, 0, cur);
			visited[u][v + 1] = 0;
		}

		if (map[u][v + 1] == 0 && map[u + 1][v + 1] == 0 && map[u + 1][v] == 0) {
			if (visited[u][v + 1] == 0 && visited[u + 1][v + 1] == 0 && visited[u + 1][v] == 0) {
				visited[u + 1][v + 1] = 1;
				dfs(u + 1, v + 1, 1, cur);
				visited[u + 1][v + 1] = 0;
			}
		}

		if (map[u + 1][v] == 0 && visited[u + 1][v] == 0) {
			visited[u + 1][v] = 1;
			dfs(u + 1, v, 2, cur);
			visited[u + 1][v] = 0;
		}
	}

	else if ((before == 1 || before == 2) && cur == 2) {
		if (map[u][v + 1] == 0 && map[u + 1][v + 1] == 0 && map[u + 1][v] == 0) {
			if (visited[u][v + 1] == 0 && visited[u + 1][v + 1] == 0 && visited[u + 1][v] == 0) {
				visited[u + 1][v + 1] = 1;
				dfs(u + 1, v + 1, 1, cur);
				visited[u + 1][v + 1] = 0;
			}
		}

		if (map[u + 1][v] == 0 && visited[u + 1][v] == 0) {
			visited[u + 1][v] = 1;
			dfs(u + 1, v, 2, cur);
			visited[u + 1][v] = 0;
		}
	}
}

int main(void) {

	scanf("%d", &n);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			scanf("%d", &map[y][x]);
		}
	}

	visited[0][0] = 1, visited[0][1] = 1;
	dfs(0,1,0,0);

	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}