백준 17070번 파이프 옮기기 1(C++)

 

가장 먼저 생각할 수 있는 방법은 DFS였다. 최소로 이동하는 것도 아니고 각 지점마다 움직일 수 있는 방법이 한정되어있다. 각 노드에서 따질 것이 많다면 DFS가 유리하다. 각 지점마다 방향의 상태를 지정해줘야하기 때문이다.

그런데 이 문제를 보면 시간제한이 1초로 빡세지만 집의 크기가 무려 3~16으로 매우 편하게 주었다. N이 조금만 커져도 이 문제는 dfs bfs로 풀 수 없다. 나름 잘 풀었다고 생각했는데도 시간은 104ms로 오래걸렸다.

 

이 문제의 의도는 다이나믹 프로그래밍이다. dfs로 최적화하는법도 있겠지만 이문제는 온리 DP로만 풀이가 가능한 것 같다. 채점 현황을 보니 골드 하위정도 티어들은 모두 그래프로 풀고 골드 상위부턴 DP로 풀이했다. 다음에 DP로 다시 풀어봐야겠다.

 

1. 맨 처음은 가로로 놓여있으니 방향표시를 가로로 둔다,

2. 각 방향마다 이동가능한 dx dy 배열을 만들어 놓는다.

3. 방향마다 이동 가능한 만큼 반복하여 dfs

4. 끝까지 deep 했는데 n,n이 아니면 그대로 끝나고 끝까지 갔는데 n,n 이면 cnt++

#include<iostream>
#define MAX 17
using namespace std;

int boad[MAX][MAX] = { 0, };
int N;
int cnt = 0;

int dx1[] = { 1, 0 };
int dy1[] = { 1, 1 };
int dx2[] = { 1, 1 };
int dy2[] = { 0, 1 };
int dx3[] = { 0,1,1 };
int dy3[] = { 1,0,1 };
 
void dfs(int direct, int x, int y) {
	if (x == N - 1 && y == N - 1) {
		cnt++;
	}
	if (direct == 1) {			// 가로
		for (int i = 0; i < 2; i++) {
			int nx = x + dx1[i];
			int ny = y + dy1[i];
			if (nx < N && nx > -1 && ny < N && ny > -1 && boad[nx][ny] == 0) {
				if (i == 0 && boad[nx - 1][ny] == 0 && boad[nx][ny - 1] == 0) {
					dfs(3, nx, ny);
				}
				else if (i == 1) {
					dfs(1, nx, ny);
				}
			}
		}
	}
	else if (direct == 2) {		// 세로
		for (int i = 0; i < 2; i++) {
			int nx = x + dx2[i];
			int ny = y + dy2[i];

			if (nx < N && nx > -1 && ny < N && ny > -1 && boad[nx][ny] == 0) {
				if (i == 0) {
					dfs(2, nx, ny);
				}
				else if (i == 1 && boad[nx - 1][ny] == 0 && boad[nx][ny - 1] == 0) {
					dfs(3, nx, ny);
				}
			}
		}
	}
	else if (direct == 3) {		// 대각선
		for (int i = 0; i < 3; i++) {
			int nx = x + dx3[i];
			int ny = y + dy3[i];

			if (nx < N && nx > -1 && ny < N && ny > -1 && boad[nx][ny] == 0) {
				if (i == 0) {
					dfs(1, nx, ny);
				}
				else if (i == 1) {
					dfs(2, nx, ny);
				}
				else if (i == 2 && boad[nx - 1][ny] == 0 && boad[nx][ny - 1] == 0) {
					dfs(3, nx, ny);
				}
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> boad[i][j];
		}
	}
	dfs(1, 0, 1);
	cout << cnt;
	return 0;
}