https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
그래프와 dp 연계 문제입니다.
파이프가 가로로 놓여있을 때, 세로로 놓여있을 때, 대각선으로 놓여있을 때 이동방법과 벽 위치 여부를 고려하여 dfs로 파이프를 움직여주고, 파이프의 한쪽 끝이 N, N에 도달하는 경우의 수를 dp를 이용하여 구해주시면 되겠습니다.
dfs만 쓰게 되면 파이프가 같은 위치로 여러번 탐색하게 되며 시간초과가 발생하게 됩니다.
따라서 dp를 사용하여 파이프가 방문한 위치에서는 해당위치의 경우의 수를 리턴해주면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <iostream>
#include <cstring>
using namespace std;
int list[17][17], dp[17][17][17][17];
int N, ans;
int dfs(int fx, int fy, int sx, int sy) {
if (sx > N || sy > N) return 0;
if (sx == N && sy == N) return 1;
if (dp[fx][fy][sx][sy] != -1) return dp[fx][fy][sx][sy];
dp[fx][fy][sx][sy] = 0;
if (fx == sx && fy + 1 == sy) { //가로
if (!list[sx][sy + 1]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx, sy + 1);
if (!list[sx + 1][sy + 1] && !list[sx + 1][sy]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx + 1, sy + 1);
}
}
}
else if (fy == sy && fx + 1 == sx) { //세로
if (!list[sx + 1][sy]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx + 1, sy);
if (!list[sx + 1][sy + 1] && !list[sx][sy + 1]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx + 1, sy + 1);
}
}
}
else { //대각
if (!list[sx + 1][sy]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx + 1, sy);
}
if (!list[sx][sy + 1]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx, sy + 1);
}
if (!list[sx + 1][sy] && !list[sx][sy + 1] && !list[sx + 1][sy + 1]) {
dp[fx][fy][sx][sy] += dfs(sx, sy, sx + 1, sy + 1);
}
}
return dp[fx][fy][sx][sy];
}
void input() {
memset(dp, -1, sizeof(dp));
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << dfs(1, 1, 1, 2) << '\n';
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12101 1, 2, 3 더하기 2 (0) | 2021.01.22 |
|---|---|
| boj 9095 1, 2, 3 더하기 (0) | 2021.01.22 |
| boj 14226 이모티콘 (0) | 2021.01.22 |
| boj 11053 가장 긴 증가하는 부분 수열 (0) | 2021.01.22 |
| boj 1463 1로 만들기 (0) | 2021.01.22 |