백준 1600번 말이 되고픈 원숭이 C++

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

 

일반적인 bfs와 비슷한데, 큐에 넣는 정보에 말처럼 이동한 횟수를 저장하는 정보도 같이 넣어서 이미 k번 말처럼 이동했다면 한칸씩만 이동하도록 하고, 방문 검사를 말처럼 이동한 횟수에 따라 다르게 검사하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int k, w, h;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
int dRowHorse[8] = { -2,-1,1,2,2,1,-1,-2 };
int dColHorse[8] = { 1,2,2,1,-1,-2,-2,-1 };

struct PosInfo {
	int row;
	int col;
	int moveCnt;
	int horseMove;
};

bool CanGo(const vector<vector<int>>& board, vector<vector<vector<bool>>> &found, 
				int horseMove, int row, int col) {
	if (row<0 || row>=h) return false;
	if (col<0 || col>=w) return false;
	if (board[row][col] == 1) return false;
	if (found[horseMove][row][col]) return false;
	return true;
}

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

	cin >> k >> w >> h;
	vector<vector<int>> board(h, vector<int>(w));
	vector<vector<vector<bool>>> found(k + 1, vector<vector<bool>>(h, vector<bool>(w, false)));
	queue<PosInfo> q;
	pair<int, int> target = { h - 1,w - 1 };

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> board[i][j];
		}
	}

	q.push({ 0,0,0,0 });
	found[0][0][0] = true;
	int ans = -1;
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (curr.row == target.first && curr.col == target.second) {
			ans = curr.moveCnt;
			break;
		}
		if (curr.horseMove < k) {
			for (int i = 0; i < 8; i++) {
				int nextRow = curr.row + dRowHorse[i];
				int nextCol = curr.col + dColHorse[i];
				if (CanGo(board, found, curr.horseMove + 1, nextRow, nextCol)) {
					found[curr.horseMove + 1][nextRow][nextCol] = true;
					q.push({ nextRow,nextCol,curr.moveCnt + 1,curr.horseMove + 1 });
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int nextRow = curr.row + dRow[i];
			int nextCol = curr.col + dCol[i];
			if (CanGo(board, found, curr.horseMove, nextRow, nextCol)) {
				found[curr.horseMove][nextRow][nextCol] = true;
				q.push({ nextRow,nextCol,curr.moveCnt + 1,curr.horseMove});
			}
		}
	}
	cout << ans;
};