문제 자체는 DP로 분류되어 있었는데 dfs로 푸니까 간단하게 풀린 문제였다.
처음에 DP로 풀려고 하다가 시간을 많이 사용했는데 이런걸 생각하면 너무 분류에 집중해서 풀지 않아도 될 것 같다!
푸는 방법은 일단 파이프를 가로, 세로, 대각선 3가지 모드가 있다고 생각하고 각 모드에 맞게 모든 경우의 수를 진행해주었다. 크기가 최대 16*16이라 DFS가 터지지 않을 것 같았다.
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, ans;
int map[17][17];
void dfs(int x, int y, int mode) {
if (x == n && y == n) {
ans++;
return;
}
if (mode == 0 || mode == 2) {
if (y + 1 <= n && map[x][y + 1] == 0) {
dfs(x, y + 1, 0);
}
}
if (mode == 1 || mode == 2) {
if (x + 1 <= n && map[x + 1][y] == 0) {
dfs(x + 1, y, 1);
}
}
if (x + 1 <= n && y + 1 <= n && map[x + 1][y + 1] == 0
&& map[x][y+1] == 0 && map[x+1][y] == 0) {
dfs(x + 1, y + 1, 2);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
}
}
dfs(1, 2, 0);
cout << ans;
return 0;
}
'알고리즘 공부 > C++' 카테고리의 다른 글
[C++] 백준 2206번: 벽 부수고 이동하기 (0) | 2020.11.28 |
---|---|
[C++] 백준 9663번: N-Queen (0) | 2020.11.27 |
[C++] 백준 14716번: 현수막 (0) | 2020.11.26 |
[C++] 백준 13549번: 숨바꼭질 3 (0) | 2020.11.25 |
[C++] 백준 1707번: 이분 그래프 (0) | 2020.11.24 |