BOJ-1600 말이 되고픈 원숭이

필요한 지식

1. BFS

접근

• 체크배열을 chk[k][i][j] : k번째 말처럼 이동할 수 있는 횟수가 남았을때 i,j 칸에 도달 했는지 여부로 정의하고 BFS를 수행한다.

• 그 칸에 최소의 횟수로 도달했다고해서 마지막칸에 최소의 이동횟수로 도달 할 수 있는건 아니다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef struct node { int y, x, c, r; };
int k, w, h, ans = INT_MAX, arr[201][201], chk[31][201][201];
int dir[2][8][2] = { { {1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2} },{ {-1,0},{0,1},{1,0},{0,-1} } };
queue<node>q;

void move(node cur, int pp, int r, int d) {
	for (int p = 0; p < pp; p++) {
		int ny = cur.y + dir[d][p][0];
		int nx = cur.x + dir[d][p][1];
		if (0 <= ny && ny < h && 0 <= nx && nx < w && arr[ny][nx] == 0 && chk[r][ny][nx] == 0) {
			q.push(node{ ny,nx,cur.c + 1,r });
			chk[r][ny][nx] = 1;
		}
	}
}
void bfs() {
	q.push(node{ 0,0,0,k });
	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		if (cur.y == h - 1 && cur.x == w - 1) {
			ans = min(ans, cur.c);
			continue;
		}
		if (cur.r > 0) move(cur, 8, cur.r - 1, 0);
		move(cur, 4, cur.r, 1);
	}
	return;
}
int main() {
	FIO;
	cin >> k >> w >> h;
	for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> arr[i][j];
	bfs();
	ans = (ans == INT_MAX) ? -1 : ans;
	cout << ans;
	return 0;
}

결과