(1, 1) 에서 시작하여 (N, N) 까지 파이프를 옮기는 경우의 수를 찾는 문제
완전탐색으로 풀어야 한다.
방향은 (0) 오른쪽, (1) 대각선아래, (2) 아래쪽 으로 총 3가지가 존재한다.
파이프는 정해진 방향으로만 밀 수 있다.
정해진 방향이 의미하는 것은 '현재 방향 상태'에 따라 가볼 수 있는 경우의 수가 달라진다는 것을 의미한다.
이를 표로 나타냄.
현재 방향 | 다음 방향 |
---|---|
0 (오른쪽) | (0) 오른쪽, (1) 대각선아래 |
(1) 대각선아래 | (0) 오른쪽, (1) 대각선아래, (2) 아래쪽 |
(2) 아래쪽 | (1) 대각선아래, (2) 아래쪽 |
현재 방향에 따라 갈 수 있는 다음 방향은 위와 같다.
이를 벡터 V에 하드코딩하여 정의하여 사용.
현재 방향에 따라 갈 수 있는 다음 방향이 있다.
그러므로 각각의 방향으로 향했을 때 해당 좌표가 valid한지 확인한 후 이동 가능 여부를 반환하게 하였다.
구현: test_pass()
#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;
}
직전에 풀었던 문제에 비하면 난이도가 쉬웠다.