[백준 17070] 파이프 옮기기1

분류 

dfs, 구현

요구사항

파이프를 옮겨서 (n,n)으로 이동 시킬때, 가장 작은 이동 횟수로 파이프 옮기기

풀이

가로 일때, 취할 수 있는 경우 2가지

세로 일때, 2가지

대각 선일때, 3가지 경우의 수로 이동할 수 있다.

7가지 경우의 수 밖에 없으니

총 7가지 경우의 수가 있고, 현재 가로, 세로, 대각에 따라 2,2,3가지의 경우의 수 밖에 없다.

각각의 좌표를 구해준 뒤, 가능하면 이동하는 식으로 풀이한다.

 

#include <iostream>

using namespace std;
int map[18][18];
int visit[18][18];
int n;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;
int garo_r(int r) {
	return r + dr[3];
}
int garo_c(int c) {
	return c + dc[3];
}
int sero_r(int r) {
	return r + dr[2];
}
int sero_c(int c) {
	return c + dc[2];
}
int cross_r(int r) {
	return r + dr[2];
}
int cross_c(int c) {
	return c + dc[3];
}
void show() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << visit[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void solve(int sr, int sc, int er, int ec, int state) {
	//1번 가로로 놓아져있을때는 2가지로 갈 수 있다.
	if (er == n - 1 && ec == n - 1) {
		ans++;
		return;
	}
	if (state == 1) {
		int nr = garo_r(sr);
		int nc = garo_c(sc);
		int nnr = garo_r(er);
		int nnc = garo_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				visit[nr][nc] = 1;
				visit[nnr][nnc] = 2;
				solve(nr, nc, nnr, nnc, 1);
				visit[nnr][nnc] = 0;
				visit[nr][nc] = 0;
			}
		}
		nr = garo_r(sr);
		nc = garo_c(sc);
		nnr = cross_r(er);
		nnc = cross_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				if (map[nr + 1][nc] == 0 && map[nr][nc + 1] == 0) {
					//		cout<<"1 cross"<<endl;
					visit[nr][nc] = 1;
					visit[nnr][nnc] = 2;
					solve(nr, nc, nnr, nnc, 2);
					visit[nnr][nnc] = 0;
					visit[nr][nc] = 0;
				}
			}
		}
	}

	if (state == 2) {
		int nr = cross_r(sr);
		int nc = cross_c(sc);
		int nnr = garo_r(er);
		int nnc = garo_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				//	cout<<"2 garo"<<endl;
				visit[nr][nc] = 1;

				visit[nnr][nnc] = 2;
				solve(nr, nc, nnr, nnc, 1);
				visit[nnr][nnc] = 0;
				visit[nr][nc] = 0;
			}
		}
		nnr = cross_r(er);
		nnc = cross_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				if (map[nr + 1][nc] == 0 && map[nr][nc + 1] == 0) {
					//		cout<<"2 cross"<<endl;
					visit[nr][nc] = 1;
					visit[nnr][nnc] = 2;
					solve(nr, nc, nnr, nnc, 2);
					visit[nnr][nnc] = 0;
					visit[nr][nc] = 0;
				}
			}
		}
		nnr = sero_r(er);
		nnc = sero_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				//		cout<<"2 sero"<<endl;
				visit[nr][nc] = 1;
				visit[nnr][nnc] = 2;
				solve(nr, nc, nnr, nnc, 3);
				visit[nnr][nnc] = 0;
				visit[nr][nc] = 0;
			}
		}
	}

	if (state == 3) {
		int nr = sero_r(sr);
		int nc = sero_c(sc);
		int nnr = sero_r(er);
		int nnc = sero_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				//		cout<<"3 sero"<<endl;
				visit[nr][nc] = 1;
				visit[nnr][nnc] = 2;
				solve(nr, nc, nnr, nnc, 3);
				visit[nnr][nnc] = 0;
				visit[nr][nc] = 0;
			}
		}
		nnr = cross_r(er);
		nnc = cross_c(ec);
		if (nr >= 0 && nc >= 0 && nr<n && nc<n && nnr >= 0 && nnc >= 0 && nnr<n && nnc< n) {
			if (map[nr][nc] == 0 && map[nnr][nnc] == 0) {
				if (map[nr + 1][nc] == 0 && map[nr][nc + 1] == 0) {
					//			cout<<"3 cross"<<endl;
					visit[nr][nc] = 1;
					visit[nnr][nnc] = 2;
					solve(nr, nc, nnr, nnc, 2);
					visit[nnr][nnc] = 0;
					visit[nr][nc] = 0;
				}
			}
		}
	}

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

	solve(0, 0, 0, 1, 1);
	cout << ans << endl;

}