[BOJ][삼성기출] 17010. 파이프 옮기기1

문제

파이프 옮기기 1

첫인상

(1, 1) 에서 시작하여 (N, N) 까지 파이프를 옮기는 경우의 수를 찾는 문제
완전탐색으로 풀어야 한다.

0. 파이프를 옮길 수 있는 방향

방향은 (0) 오른쪽, (1) 대각선아래, (2) 아래쪽 으로 총 3가지가 존재한다.
파이프는 정해진 방향으로만 밀 수 있다.
정해진 방향이 의미하는 것은 '현재 방향 상태'에 따라 가볼 수 있는 경우의 수가 달라진다는 것을 의미한다.

이를 표로 나타냄.

현재 방향	다음 방향
0 (오른쪽)	(0) 오른쪽, (1) 대각선아래
(1) 대각선아래	(0) 오른쪽, (1) 대각선아래, (2) 아래쪽
(2) 아래쪽	(1) 대각선아래, (2) 아래쪽

현재 방향에 따라 갈 수 있는 다음 방향은 위와 같다.
이를 벡터 V에 하드코딩하여 정의하여 사용.

1. 모든 경우 탐색

현재 방향에 따라 갈 수 있는 다음 방향이 있다.
그러므로 각각의 방향으로 향했을 때 해당 좌표가 valid한지 확인한 후 이동 가능 여부를 반환하게 하였다.
구현: test_pass()

문제 접근

문제 흐름

1. (1, 2) 에서부터 시작하여 가능한 위치로 이동한다.
2. 매 이동 마다 (N, N)에 다다랐는지 확인하고, (N, N)일 경우 rst를 1씩 증가시킨다.

풀이

#include <iostream>
#include <vector>
using namespace std;

int N, rst, Dir, Nx, Ny;
int map[17][17];
int dx[] = { 0, 1, 1 }; 
int dy[] = { 1, 1, 0 };
vector<int> V[3];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	rst = 0;	
	V[0].push_back(0); V[0].push_back(1);
	V[1].push_back(0); V[1].push_back(1); V[1].push_back(2);
	V[2].push_back(1); V[2].push_back(2);
}

int is_range(int x, int y) {
	if (x >= 1 && x <= N && y >= 1 && y <= N) return true;
	return false;
}

int test_pass(int x, int y, int dir) { // 좌표 (x,y) 에서 dir 방향으로 이동할 수 있는지 확인
	if (dir == 1) { // 대각선: 3가지 방향 확인
		bool flag = true;
		for (int d = 0; d <= 2; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (map[nx][ny] == 1 || !is_range(nx, ny)) { // 벽이거나, 범위 밖일 경우
				flag = false; 
				break;
			}
		}
		if (flag) {
			Nx = x + dx[dir];
			Ny = y + dy[dir];
			Dir = dir;
			return true;
		}
	}
	else { // 오른쪽, 아래
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (map[nx][ny] != 1 && is_range(nx, ny)) {
			Nx = nx; Ny = ny; Dir = dir;
			return true;
		}
	}
	return false;
}

void dfs(int x, int y, int dir) {
	if (x == N && y == N) {
		rst++;
		return;
	}
	for (int i = 0; i < V[dir].size(); i++) {
		if (test_pass(x, y, V[dir][i])) {
			dfs(Nx, Ny, Dir);
		}
	}
}

void solve() {
	for (int i = 0; i < V[0].size(); i++) {
		if (test_pass(1, 2, V[0][i])) {
			dfs(Nx, Ny, Dir);
		}
	}
 }

int main() {
	input();
	solve();
	cout << rst << endl;
}

직전에 풀었던 문제에 비하면 난이도가 쉬웠다.