17070 - 파이프 옮기기 1
본문
유현이가 새 집으로 이사했다. 새 집의 크기는 $N \times N$의 격자판으로 나타낼 수 있고, $1 \times 1$크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 ($r, c$)로 나타낼 수 있다. 여기서 $r$은 행의 번호, $c$는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
가장 처음에 파이프는 ($1, 1$)와 ($1, 2$)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 ($N, N$)로 이동시키는 방법의 개수를 구해보자.
입력
첫째 줄에 집의 크기 $N$ ($3 \leq N \leq 16$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 집의 상태가 주어진다. 빈 칸은 $0$, 벽은 $1$로 주어진다. ($1, 1$)과 ($1, 2$)는 항상 빈 칸이다.
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 512MB |
- $3 \leq N \leq 16$
풀이
간단한 dp문제이다. 심지어 각 위치마다 새로운 상황이 나타나는 것도 아니고, 기존의 결과를 그대로 가져와서 사용하므로 dp의 기본형이라고도 할 수 있을만한 문제다.
일단 dp문제니까 dp배열에 무엇을 저장할지를 정해야한다. 파이프를 설치하는 위치가 16x16 크기의 grid이므로 일단 dp[16][16]으로 만들고 생각하자. 파이프를 설치할 수 있는 방법은 가로, 세로, 대각선 총 3개인데, 이전 상태가 어떤 상태였는가에 따라 설치할 수 있는 모양이 다르다. 그래서 현재 위치까지 설치할 수 있는 파이프를 가로, 세로, 대각선에 따라 각각 따로 저장해두면 계산하기 편할 것 같다. 그래서 dp[16][16][3] : “현재 위치에 특정 모양의 파이프를 설치할 수 있는 경우의 수”로 저장해두도록 하자.
가로, 세로, 대각선 파이프를 설치할 수 있는 조건을 정리하자. 간단히 정리해두면 구현할 때 점화식을 만들기 쉬워진다.
- $(i, j)$ 칸에 가로 파이프를 설치하려는 경우
- $(i, j)$ 칸이 빈칸이어야 한다
- $(i, j-1)$ 칸의 파이프는 가로 or 대각선 파이프로 설치되었어야만 한다
- $(i, j)$ 칸에 세로 파이프를 설치하려는 경우
- $(i, j)$ 칸이 빈칸이어야 한다
- $(i, j-1)$ 칸의 파이프는 세로 or 대각선 파이프로 설치되었어야만 한다
- $(i, j)$ 칸에 대각선 파이프를 설치하려는 경우
- $(i-1, j)$, $(i, j-1)$, $(i, j)$ 칸이 빈칸이어야 한다
- $(i-1, j-1)$ 칸의 파이프는 가로 or 세로 or 대각선 파이프로 설치되었어야만 한다 (모든 경우가 가능하다)
dp배열도 정했고 점화식 분기점도 구했다. 분기점에 ‘~~칸이 빈칸이어야한다’ 라는 조건이 있는데, 이 문제에서는 벽이 존재하기 때문에, 그곳에는 파이프를 설치할 수 없다는 점도 생각해야한다.
- 참고 알고리즘 : 다이나믹 프로그래밍
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 18
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define SPACE 0
#define WALL 1
#define HORIZONTAL 0
#define VERTICAL 1
#define DIAGONAL 2
#define MAX_IDX 16
bool grid[MAX_IDX][MAX_IDX];
int dp[MAX_IDX][MAX_IDX][3];
int n;
int startX = 0, startY = 1;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int a;
scanf("%d", &a);
grid[i][j] = a;
}
}
dp[startX][startY][HORIZONTAL] = 1;
// first layer
for (int i = 2; i < n; ++i) {
if (grid[startX][i] == WALL) {
break;
}
dp[startX][i][HORIZONTAL] = 1; // only horizontal can fix
}
// other layer
for (int i = 1; i < n; ++i) {
for (int j = 1; j < n; ++j) {
if (grid[i][j] == SPACE) {
dp[i][j][HORIZONTAL] = dp[i][j - 1][HORIZONTAL] + dp[i][j - 1][DIAGONAL];
dp[i][j][VERTICAL] = dp[i - 1][j][VERTICAL] + dp[i - 1][j][DIAGONAL];
if (grid[i - 1][j] == SPACE && grid[i][j - 1] == SPACE) {
dp[i][j][DIAGONAL] = dp[i - 1][j - 1][HORIZONTAL] + dp[i - 1][j - 1][VERTICAL] + dp[i - 1][j - 1][DIAGONAL];
}
}
}
}
printf("%d", dp[n - 1][n - 1][HORIZONTAL] + dp[n - 1][n - 1][VERTICAL] + dp[n - 1][n - 1][DIAGONAL]);
return 0;
}
grid[][]: 입력으로 주어지는 칸의 상태dp[][][3]: 특정 방법 (가로 / 세로 / 대각선) 으로 현재 위치에 파이프를 설치할 수 있는 경우의 수를 기록HORIZONTAL: 가로 방법으로 파이프를 설치VERTICAL: 세로 방법으로 파이프를 설치DIAGONAL: 대각선 방법으로 파이프를 설치