백준 - 17070번, 파이프 옮기기 1 문제 BFS 방식 풀이 (with C++)

문제 설명

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈칸만 차지해야 한다.

 

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

 

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓인 경우에는 2가지, 대각선 방향으로 놓인 경우에는 3가지가 있다.

 

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈칸이어야 하는 곳은 색으로 표시되어 있다.

 

가로

세로

대각선

 

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

---

입력

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈칸이다.

---

출력

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

---

내 풀이 설명

파이프는 총 세 가지 방향으로 움직일 수 있고, 또 현재 파이프가 놓인 방향에 따라 이동할 수 있는 방향이 갈립니다. 따라서 단순하게 BFS 혹은 DFS 방식으로 문제를 풀이하되, 이동 가능한 방향에 대한 조건 + 파이프와 인접한 곳에 벽이 있는지 여부에 따라 queue에 다음에 방문할 위치를 기록하도록 구현했습니다.

 

또한 집의 (n, n) 좌표에 도달하면, cnt 변수를 +1 하도록 구현하여 도착 지점으로 향하는 경로의 수를 count 했습니다.

 

구현하는 부분에서 크게 까다로운 부분은 없었지만, 구현 요구 사항이 많은 점이 조금 문제를 어렵게? 만든 것 같았지만, 그래도 문제에서 설명된 바를 지키면 큰 어려움 없이 풀이가 가능한 유형의 문제인 것 같습니다!! 😁😁

 

추가적으로 파이프가 움직이는 방식을 고려했을 때, BFS 방식으로 탐색할 시 중복되는 경로를 counting 하는 것은 불가능하여 따로 방문 처리를 한다거나 하지 않아도 문제를 해결할 수 있었습니다.

---

제출 코드 (C++)

#include <iostream>
#include <queue>
#define MAX 17

using namespace std;

int n;
int home[MAX][MAX];

bool inRange(int x, int y) {
	return (0 <= x && x < n && 0 <= y && y < n);
}

bool checkDir(int cur_dir, int next_dir) {
	if (cur_dir == 0 && next_dir == 2)
		return false;
	else if (cur_dir == 2 && next_dir == 0)
		return false;
	else
		return true;
}

int BFS() {
	// tail의 좌표, 방향
	queue<pair<pair<int, int>, int>> q;
	int res = 0;

	// (우, 우하, 하) 세 가지의 방향으로 이동할 수 있다.
	int dx[] = { 0, 1, 1 };
	int dy[] = { 1, 1, 0 };

	// 파이프의 초기 위치는 (0, 0), (0, 1) 이다.
	q.push({ {0, 0}, 0 });

	while (!q.empty()) {
		int tail_x = q.front().first.first, tail_y = q.front().first.second;
		int dir = q.front().second;
		int head_x = tail_x + dx[dir], head_y = tail_y + dy[dir];

		q.pop();

		if (head_x == n - 1 && head_y == n - 1) {
			res++;
			continue;
		}

		for (int i = 0; i < 3; i++) {
			if (!checkDir(dir, i))
				continue;

			int next_head_x = head_x + dx[i];
			int next_head_y = head_y + dy[i];

			// 집을 벗어나는 경우는 스킵한다.
			if (!inRange(next_head_x, next_head_y))
				continue;

			// 벽이 있는 경우도 못간다.
			bool isThereWall = false;
			for (int i = head_x; i <= next_head_x; i++) {
				for (int j = head_y; j <= next_head_y; j++) {
					if (home[i][j] == 1)
						isThereWall = true;
				}
			}
			if (isThereWall) continue;

			q.push({ {head_x, head_y}, i });
		}

	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> home[i][j];
		}
	}

	cout << BFS();

	return 0;
}