[baekjoon 17070] 파이프 옮기기 1 (DFS, 백트래킹) (C++)

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

파이프를 옮겨서 주어진 사이즈의 끝점까지 옮길 수 있는 경우의 수를 찾는 문제이다.

신경 써줘야 할 점은

가로로 옮긴 다음엔 가로 OR 대각선

세로로 올긴 다음엔 세로 OR 대각선

대각선으로 옮긴 다음엔 가로 OR 세로 OR 대각선이 모두 가능하다.

또한 대각선으로 옮길 때에는 다음 나아갈 점뿐만 아니라 그 점의 위와 왼쪽 또한 벽이 없어야 한다.

 

이 조건만 잘 지켜주면서 모든 경우의 수를 탐색해주면 된다. (N이 최대 16이라 가능하다고 생각했다.)

 

처음엔 DFS+DP를 통해 미리 방문한 경로이면 dp값을 더해줘서 풀려고 했는데 이 방법을 사용하면 이미 방문한 길이 가로를 통해 방문했지만 나는 현재 세로인 상태에서 방문해버리면 틀리는 경우가 나오므로 방법을 바꿨다.

 

그냥 DFS로 탐색 + 백 트래킹 해주면서 모든 경우의 수를 찾았다. 

추가로, DFS의 파라미터에 어떤 방향으로 진행했는지 direction 변수를 넣어서 예외처리를 했다.

#include <iostream>

using namespace std;

int n, arr[17][17], xmove[3] = { 0, 1, 1 }, ymove[3] = { 1, 0, 1 };
int record[17][17], answer;

void DFS(int x, int y, int direction) {
	if (x == n - 1 && y == n - 1) {
		answer++;
		return;
	}

	for (int i = 0; i < 3; i++) {
		if (direction == 0 && i == 1)
			continue;
		else if (direction == 1 && i == 0)
			continue;
		else {
			int nx = x + xmove[i];
			int ny = y + ymove[i];

			if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
				if (i == 0 || i == 1) {
					if (arr[nx][ny] == 0 && !record[nx][ny]) {
						record[nx][ny] = true;
						DFS(nx, ny, i);
						record[nx][ny] = false;
					}
				}
				else {
					if (arr[nx][ny] == 0 && arr[nx-1][ny] == 0 && arr[nx][ny-1] == 0 && !record[nx][ny]) {
						record[nx][ny] = true;
						DFS(nx, ny, i);
						record[nx][ny] = false;
					}
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	DFS(0, 1, 0);

	cout << answer;
}

direction은 0은 가로, 1은 세로, 2는 대각선이므로

만약 0인데 1이면 (가로-세로)의 경우이므로 continue

마찬가지로 1인데 0이면(세로-가로) continue 해주었고

이번에 나아갈 방향이 2(대각선)이면 추가로 주변에 벽이 있는지 체크해주었다.