https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
<풀이>
1. 집의 상태를 입력받는다.
2. 파이프를 한쪽 끝으로 옮길 수 있는 방법의 수를 출력한다.
<해법>
1. 알고리즘 선택하기
=> 모든 방법의 수를 구해야하므로, 파이프를 놓는 모든 경우를 다 해보아야합니다. 따라서, 저는 백트래킹을 선택하였습니다.(파이프를 놓을 수 있는 유망한 경우에만 탐색할 것이므로)
2. 파이프 옮기기
=> 파이프는 종류에 따라 (1)다음에 놓을 파이프가 다르고, (2)파이프를 놓을 수 있는 공간이 다릅니다. 따라서, 저는 위 두가지 경우를 배열로 미리 만들어 놓았습니다.(코드의 connect[][]와 check[][] 참조)
3. 최적화 할 수 있을까?
=> 이 문제는 작은 부분 문제에서 구한 최적의 답을 이용해서 큰 문제의 최적의 답을 구할 수 있습니다. 따라서, 저는 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
#include <iostream>
#include <string.h>
using namespace std;
int dx[] = { 0,1,1 };
int dy[] = { 1,0,1 };
int connect[3][3] = { //파이프 끼리 연결 가능 여부
{1,0,1},
{0,1,1},
{1,1,1},
};
int check[3][3] = { //파이프를 놓을 때, 확인해야하는 부분
{1,0,0},
{0,1,0},
{1,1,1}
};
int N;
int map[16][16];
int cache[16][16][3];
int answer;
bool isInner(int x, int y) {
if (x < 0 || y < 0 || x >= N || y >= N) return false;
return true;
}
bool canMove(int x, int y, int type) {
for (int i = 0; i < 3; i++) {
if (!check[type][i]) continue;
int nx = x + dx[i];
int ny = y + dy[i];
if (!isInner(nx, ny) || map[nx][ny] == 1) return false;
}
return true;
}
int movePipe(int x, int y, int type) {
if (x == N - 1 && y == N - 1) return 1;
int& ret = cache[x][y][type];
if (ret != -1) return ret;
ret = 0;
for (int i = 0; i < 3; i++) {
if (connect[type][i] && canMove(x, y, i)) {
ret += movePipe(x + dx[i], y + dy[i], i);
}
}
return ret;
}
void solution() {
answer = movePipe(0, 1, 0);
}
int main() {
//초기화
N = 0;
memset(map, 0, sizeof(map));
memset(cache, -1, sizeof(cache));
answer = 0;
//입력
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
//해법
solution();
//출력
cout << answer << "\n";
//종료
return 0;
}
|
백트래킹과 DP에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 17136 - 색종이 붙이기 (0) | 2022.12.22 |
|---|---|
| [C++] 백준 17135 - 캐슬 디펜스 (0) | 2022.12.21 |
| [C++] 백준 16637 - 괄호 추가하기 (0) | 2022.12.21 |
| [C++] 백준 13460 - 구슬 탈출2 (1) | 2022.12.21 |
| [C++] 백준 2011 - 암호코드 (0) | 2021.02.06 |
