[C++] BOJ(백준) 1600 말이 되고픈 원숭이

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

BFS 문제다.

 

문제를 해결하기 위해 돌아온 길이 많아서 시행착오는 후에 작성하겠다.

문제 해결은 일반 BFS에 8방향 검사를 추가로 시행했다.

방문 배열을 3차원으로 설정해 8방향 이동 능력을 몇 번 사용했는지 체크했다.

간단한데도 이 방법을 생각해내는데 오래 걸렸다...

 

그리고 이 문제에서 오류가 발생하기 쉬운 점은 입력이 세로 가로가 아닌 가로 세로인 점이다.

세로를 먼저 입력받는 것이 익숙하기 때문에 m, n으로 입력을 받고 사용은 n, m을 했다.

 

#include <iostream>
#include <queue>
using namespace std;

int k, n, m;
int board[200][200];
bool visit[200][200][31];

// 상하좌우 탐색을 위함
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

// 말의 8방향 이동을 위함
int hr[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int hc[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

void BFS() {
	// <horse, <r, c>>
	queue<pair<int, pair<int, int>>> q;

	board[0][0] = 1;
	q.push({ 0, { 0, 0 } });

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curr = q.front().second.first;
		int curc = q.front().second.second;
		int cnt = q.front().first;

		q.pop();

		// 말의 8방향 이동
		if (cnt < k) {
			for (int i = 0; i < 8; i++) {
				int r = curr + hr[i];
				int c = curc + hc[i];

				// 범위를 벗어나면 continue
				if (r < 0 || c < 0 || r >= n || c >= m) continue;

				// 도착지에 도달하면 종료
				if (r == n - 1 && c == m - 1) {
					cout << board[curr][curc];
					return;
				}

				// 벽이 있다면 continue
				if (board[r][c] == -1) continue;

				// 방문한 적이 있고 능력을 사용한 횟수가 같다면 continue
				if (visit[r][c][cnt + 1]) continue;

				board[r][c] = board[curr][curc] + 1;
				visit[r][c][cnt + 1] = 1;
				q.push({ cnt + 1, { r, c } });
			}
		}

		for (int i = 0; i < 4; i++) {
			int r = curr + dr[i];
			int c = curc + dc[i];

			// 범위를 벗어나면 continue
			if (r < 0 || c < 0 || r >= n || c >= m) continue;

			// 도착지에 도착하면 종료
			if (r == n - 1 && c == m - 1) {
				cout << board[curr][curc];
				return;
			}

			// 벽이 있다면 continue
			if (board[r][c] == -1) continue;

			// 방문한 적이 있고 능력을 사용한 횟수가 같다면 continue
			if (visit[r][c][cnt]) continue;

			board[r][c] = board[curr][curc] + 1;
			visit[r][c][cnt] = 1;
			q.push({ cnt, { r, c } });
		}
	}
	cout << -1;
}

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> k >> m >> n;
	
	if (m == n && m == 1) {
		cout << 0;
		return 0;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j]) board[i][j] = -1;
		}

	BFS();
}

 

// 돌고 돌아온 시행착오

 

처음에는 단순히 4방향 검사 + 말의 8방향 검사를 해주고, 횟수 제한은 이동 수로 체크를 했다.

1
5 2
0 0 0 1 0
0 0 1 0 0

위의 예시가 입력으로 들어온다면 말의 이동 방법은 뒤 쪽에서 장애물을 넘을 때 사용해야 하는데

처음에 생각한 방법으로는 시작하자마자 써버리고 장애물을 넘을 수 없게 된다.

 

위의 경우를 해결하기 위해 4방향으로 이동했을 때만 방문 체크를 하고

4방향 이동 시 방문한 곳은 들리지 않게 했다.

즉, 8방향으로 이동한 곳에 4방향으로 이동이 가능하게 했다.

 

3
8 8
0 0 1 1 1 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 1 0 1 1
0 0 1 1 1 0 1 1
0 1 1 0 0 0 1 1
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0

위의 예시는 (0, 1) -> (1, 3) / (4, 3) -> (3, 2) / (5, 0) -> (7, 1) 에서 8방향 이동을 사용해야 한다.

 

아래 사진은 while문을 돌 때마다 몇 번 째 이동인지 확인한 것이다.

중간 사진에서 (4, 4)의 5는 왼쪽 사진의 (2,5)의 4에서 8방향 이동으로 움직인 것이다. 

오른쪽 사진에서 (4, 3)의 6은 (3, 5)의 8방향으로 움직인 것이다.

그 후 같은 자리에 (4, 4)의 5로 인해 다시 6이 된다. 여기서 방문 체크가 된다. (1)

그러나 ㄷ이 뒤집어진 곳에서 이동할 때는 8방향 이동을 하지 않아야 도착할 수 있다.

즉, (1, 5)의 5가 4방향 이동만으로 (4,3)까지 도달해야 한다.

이미 위의 (1)에서 방문 체크가 되었기 때문에 도달할 수 없고 -1이  출력된다.

답은 20이 나와야 한다.

 

이 외에도 4방향 8방향의 탐색 순서를 바꿔도 값이 달라지기도 했다.