JUST WRITE IT. HomeArchivesTagsCategories
백준 17070번 파이프 옮기기 1
|AlgorithmBOJ|

#17070. 파이프 옮기기 1

문제링크

Problem

  • 파이프는 2개의 연속된 칸을 차지
  • 회전이 가능 (3가지: 수평선, 수직선, 대각선(4칸 차지))

Goal: (0, 0) 과 (0, 1)에 위치한 하나의 파이프를 (N, N)으로 옮기는 방법의 개수
불가능한 경우 0

  • 파이프 옮기기

오른쪽, 아래, 오른쪽 아래 대각선 방향으로 옮길 수 있음
옮길 때 45도 회전 가능
벽에 닿으면 안됨

  • 가로(수평) → 오른쪽 or 오른쪽 아래 대각선
  • 세로(수직) → 아래 or 오른쪽 아래 대각선
  • 오른쪽 아래 대각선 → 3가지 모두 가능

입력

N: 3~16
빈칸 0 벽은 1
// 예제
0 0 1 0 
0 0 0 0 
0 0 0 0
0 0 0 0
-> 0

맨 처음 파이프는 (0,0), (0,1) 즉 가로이기에 가능한 방향인
오른쪽, 오른쪽 아래 대각선으로 옮길 수 없다.

Solution

  • 현재 type 정보와 위치를 알고 있어야 한다.
  • 현재 type에 따라 옮길 수 있는 방향이 다르다.
  • 현재 type에 따라 옮길 수 있는지 check를 해주어야 한다.
  • check
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    가로: 오른쪽 1칸 검사
    세로: 아래 1칸 검사
    대각선: 오른쪽 1칸, 아래 1칸, 오른쪽 아래 1칸 검사
    // # 1.
    가로 -> 가로 (자기 자신)
         -> 대각선		 
    // # 2.
    세로 -> 세로 (자기 자신)
         -> 대각선		 
    // # 3.
    대각선 -> 세로
           -> 가로
           -> 대각선
  1. 모두 자기 자신의 타입 그대로 옮길 수 있다.
  2. 대각선을 가기 위해서는 가로, 세로로 갈 수 있는 조건 역시 만족해야 한다.

위를 이용하여 탐색 코드를 구현한다.

1
2
3
4
5
6
7
8
void 탐색(현재 위치, 현재 타입)
	도착했을 때 answer++후 리턴
	for(3번)
		check할 위치(오른쪽, 아래, 오른쪽 아래)
		경계확인
			(벽이 아니고 자신과 같은 type)이거나(벽이 아니고 대각선)
				탐색(옮길 위치, 가능한 타입) 
	모든 곳을 검사했을 때만 대각선 탐색

1 Try

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
#include <cstdio>
#define MAX 16
using namespace std;
int n, answer;
int map[MAX][MAX];
bool check[MAX][MAX];
// 오른쪽 1칸 검사, 아래 1칸 검사, 오른쪽 아래 1칸 검사
int dx[3] = { 0, 1, 1 }; 
int dy[3] = { 1, 0, 1 };
bool isBound(int r, int c) {
	if (r > -1 && c > -1 && r < n && c < n) return true;
	return false;
}
// type 0 : 가로, 1 : 세로, 2 : 대각선
void dfs(int r, int c, int type) { 
	if (r == n - 1 && c == n - 1) {
		answer++;
		return;
	}
	// 현재 타입이 가로일 때 어차피 대각선 때문에 3칸 다 검사해야 한다.
	int x, y;
	bool flag = true;
	for (int i = 0; i < 3; ++i) {
		x = r + dx[i];
		y = c + dy[i];
		if (isBound(x, y)) {
// 같은 type일 경우 or 대각선일 경우, i==2이면 대각선 경우가 한 번 더 구해지는 꼴이다.
			if ((map[x][y] == 0 && type == i || map[x][y] == 0 && type == 2) && i != 2) { 
				dfs(x, y, i);
			}
			else if (map[x][y] != 0) flag = false;
		}
		else flag = false;
	}
	if (flag) {
		dfs(x, y, 2); // 오른쪽 아래 대각선
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &map[i][j]);
		}
	}
	dfs(0, 1, 0);
	printf("%d\n", answer);
	return 0;
}
Algorithm