백준 1600번: 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

---

원숭이의 좌표와 말처럼 이동할 수 있는 횟수가 몇번 남았는지에 대한 정보, 이동한 횟수를 queue에 담아서 bfs를 수행하면 원하는 결과를 얻을 수 있다.

 

한가지 유의할 점은 말처럼 이동할 경우 장애물을 뛰어넘을 수 있기 때문에 이미 방문한 좌표라도 말처럼 이동할 수 있는 횟수가 남아있느냐 남아있지 않느냐에 따라 결과값이 달라지게 된다.

따라서, 중복탐색을 피하기 위한 visited 배열을 좌표 정보만 담은 2차원 배열이 아닌, 말처럼 이동한 횟수까지 포함하는 3차원 배열로 선언해야 한다.

---

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

int K, H, W;
int board[200][200];
bool visited[200][200][31];

int dy[12] = { -1, -2, -2, -1, 1, 2, 2, 1, -1, 0, 0, 1 };
int dx[12] = { -2, -1, 1, 2, -2, -1, 1, 2, 0, -1, 1, 0 };

struct Pos {
	int y;
	int x;
};

int bfs() {
	queue<pair<pair<Pos, int>, int>> q;
	q.push({ { {0,0}, K }, 0 });
	visited[0][0][K] = true;

	while (!q.empty()) {
		int hereY = q.front().first.first.y;
		int hereX = q.front().first.first.x;
		int horse = q.front().first.second;
		int move = q.front().second;

		q.pop();

		if (hereY == H - 1 && hereX == W - 1)
			return move;

		for (int i = 0; i < 12; i++) {
			if (horse <= 0 && i < 8) continue;
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];
			if (nextY >= 0 && nextY < H && nextX >= 0 && nextX < W) {
				if (i < 8) {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse - 1]) {
						q.push({ {{nextY, nextX}, horse - 1 }, move + 1 });
						visited[nextY][nextX][horse - 1] = true;
					}
				}
				else {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse]) {
						q.push({ {{nextY, nextX}, horse}, move + 1 });
						visited[nextY][nextX][horse] = true;
					}
				}
			}
		}
	}

	return -1;
}
int main(void) {
	cin >> K >> W >> H;

	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> board[i][j];

	cout << bfs() << endl;

	return 0;
}