[BOJ] 1600 : 말이 되고픈 원숭이 (C++) with BFS

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

1600번: 말이 되고픈 원숭이

걸린 시간 : 47분 25초

---

알고리즘 아이디어

BFS의 응용판, 3차원으로 푸는 문제이다. 이와 유사한 문제가 꽤 있다. 대표적으로 벽 부수고 이동하기 문제이다. (검색 ㄱㄱ!)

벽 부수고 이동하기와 문제 조건이 거의 유사하다. 벽 부수고 이동하기 문제의 경우 벽을 부수는 행위를 할 수 있고, 말이 되고픈 원숭이 문제의 경우 말처럼 이동할 수 있는 것이다.

 

단순 BFS의 핵심은 어떤 지점에 도달했을 때 이전에 방문한 적이 없다면 그 경우가 최적의 경우인 것이다.

큐의 특성상 거리가 N인 노드들을 모두 처리한 후에 N+1인 노드들을 처리하기 때문이다. 즉 거리가 1인 노드들이 모두 처리가 끝나야 거리가 2인 노드들이 들어오므로 이전에 방문한 적이 없다면 거리가 제일 작은 최적인 것이다.

 

하지만, 이 문제에서는 어떤 지점에 나중에 도달한 경우라도 최적인지 알 수 없다. 말처럼 이동하는 경우에 제한이 있기 때문이다. 따라서 어떤 지점에 도달했을 때 말처럼 이동한 횟수를 모두 따로 처리할 것이다.

배열을 3차원으로 확장해 생각해보자. board[i][j][k] 는 board[i][j] 지점에 도달한 경우 중, 말처럼 이동한 횟수가 k번인 경우이다.

코드

• 좌표는 3차원이기 때문에 pair 자료형이 아니라 struct를 이용한다.
• 이동하는 경우인 di, dj 배열은 4 방향이 아니라 말처럼 이동하는 경우인 8방향을 포함한 12방향이다. 단, 말처럼 이동하는 경우(배열 인덱스 0~7)는 더 이상 이동할 수 없을 수도 있기 때문에 예외처리를 해야 한다.
• 결과적인 답은 dist[H-1][W-1][?] 부분을 전부 봐야 한다. 말처럼 이동한 횟수가 어찌됐든 도달한 경우를 모두 탐색해 최솟값이 답이다.
• BFS는 처리 과정이 암기가 될 정도로 숙달되어 있어야 한다. 다음 게시물의 pesudo code는 바로바로 나올 정도로 익숙해지는 것이 좋다. https://morenow.tistory.com/37

#include <bits/stdc++.h>
using namespace std;

int board[201][201];
int dist[201][201][31];
int di[12] = {-2, -1, 1, 2, 2, 1 ,-1, -2, -1, 0, 1, 0};
int dj[12] = {1, 2, 2, 1, -1, -2, -2, -1, 0, 1, 0, -1};
int K, W, H, ans = 987654321;

struct pos {
	int i, j, k;
};

void input() {
	cin >> K >> W >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> board[i][j];
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	input();
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			fill(dist[i][j], dist[i][j] + K+1, -1);
	queue<pos> q;
	q.push(pos{0, 0, 0});
	dist[0][0][0] = 0;
	while (!q.empty()) {
		int ci = q.front().i;
		int cj = q.front().j;
		int ck = q.front().k;
		q.pop();
		for (int a = 0; a < 12; a++) {
			int ni = ci + di[a];
			int nj = cj + dj[a];
			int nk = ck + ((a < 8) ? 1 : 0);
			if (nk > K && a < 8) continue;
			if (ni < 0 || ni >= H || nj < 0 || nj >= W || dist[ni][nj][nk] != -1 || board[ni][nj] == 1)
				continue;
			q.push(pos{ni, nj, nk});
			dist[ni][nj][nk] = dist[ci][cj][ck] + 1;
		}
	}
	for (int i = 0; i <= K; i++) {
		if (dist[H-1][W-1][i] == -1) continue;
		ans = min (ans, dist[H-1][W-1][i]);
	}
	if (ans == 987654321) cout << -1;
	else cout << ans;
	return 0;
}