백준 17070번

오늘 풀어본 문제는 백준의 17070번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 $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)$ 는 항상 빈 칸이다.

출력

첫째 줄에 파이프의 한쪽 끝을 $(N, N)$ 으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 $0$ 을 출력한다. 방법의 수는 항상 $1,000,000$ 보다 작거나 같다.

풀이과정

1번째 시도

문제를 보고 그래프 탐색을 이용하여 해결할 수 있는 문제라는 것을 알 수 있었다. 내가 선택한 방식은 백트래킹 방식이였고, 특정 칸에서 도착점까지 이동하는 경우의 수를 반환하는 재귀함수 travel 을 이용하여 구현하였다. 출발점은 파이프가 차지하는 오른쪽 공간으로 설정하였고, 파이프의 위치를 설정할 때는 오른쪽, 아래쪽, 혹은 남동쪽 방향의 칸으로 설정하였다.

코드는 다음과 같이 작성하였다. (문제에서 제시하는 좌표 방식과는 조금 다르게 나만의 좌표 방식을 적용하여 풀었으니 코드를 읽을 때 주의하길 바란다.)

#include <bits/stdc++.h>

constexpr auto HORIZONTAL = 0;
constexpr auto VERTICAL = 1;
constexpr auto DIAGONAL = 2;

using namespace std;

int N;
vector<int> blocked[16];

int travel(int x, int y, int type);
bool checkSpace(int x, int y);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			blocked[j].resize(N);
			cin >> blocked[j][i];
		}
	}

	int result = travel(1, 0, HORIZONTAL);
	cout << result;

	return 0;
}

int travel(int x, int y, int type) {
	int result = 0;

	if (x == N - 1 && y == N - 1) {
		return 1;
	}

	switch (type) {

	case HORIZONTAL:
		if (checkSpace(x + 1, y) == true) {
			result += travel(x + 1, y, HORIZONTAL);

			if (checkSpace(x, y + 1) == true && checkSpace(x + 1, y + 1) == true) {
				result += travel(x + 1, y + 1, DIAGONAL);
			}
		}
		break;
	
	case VERTICAL:
		if (checkSpace(x, y + 1) == true) {
			result += travel(x, y + 1, VERTICAL);

			if (checkSpace(x + 1, y) == true && checkSpace(x + 1, y + 1) == true) {
				result += travel(x + 1, y + 1, DIAGONAL);
			}
		}
		break;
	
	case DIAGONAL:
		if (checkSpace(x + 1, y) == true) {
			result += travel(x + 1, y, HORIZONTAL);
		}
		if (checkSpace(x, y + 1) == true) {
			result += travel(x, y + 1, VERTICAL);
		}
		if (checkSpace(x + 1, y) == true && checkSpace(x, y + 1) == true && checkSpace(x + 1, y + 1) == true) {
			result += travel(x + 1, y + 1, DIAGONAL);
		}
		break;

	default:
		break;
	}

	return result;
}

bool checkSpace(int x, int y) {
	if (x < 0 || x > N - 1) {
		return false;
	}
	else if (y < 0 || y > N - 1) {
		return false;
	}
	else if (blocked[x][y] == 1) {
		return false;
	}
	else {
		return true;
	}
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

문제를 풀면서 솔직히 스택 오버플로우가 나지 않을까 염려했는데, 다행히도 그런일은 일어나지 않았다. 아마 $N$의 최대 크기가 $16$으로 그리 크지 않은 값이기에 무난하게 통과한 것 같다. 그래프 탐색을 어떻게 적용해야 하는지 머리를 은근 써야했던 흥미로운 문제였다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/17070

← Previous Post Next Post →