[BOJ] 백준 1600번 : 말이 되고싶은 원숭이 C++ : 아주정은

음....벽부수고 이동하기랑 굉장히 비슷한 문제이다.

​처음에는 편하게 bfs이용해서 해봤는데 반례들이 많이 적용되었다.

처음에는 갱신형으로 풀어봣는데 반례들이 많이 발견되서 포기하고,

벽부수고 이동하기처럼 문제를 풀었다.

그리고 메모리초과가 계속 나와서 어떤 조건문이 잘못되었나 계속 찾아봤지만,

어이없게도 vis[nx][ny]=true; 이렇게 해야하는데 ==으로 쓰는바람에 메모리 초과가

계속 나타났다. 앞으로는 조심하자.

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
	int wcnt;
	int time;
};

int board[202][202];
bool vis[202][202][31];
int dx[4] = { 1,0,-1,0 };
int dy[4] = {0, 1, 0, -1};
int hx[8] = { 2,2,1,1,-1,-1,-2,-2 };
int hy[8] = { 1,-1,2,-2,2,-2,1,-1 };

int main()
{
	int k, w, h;
	cin >> k;
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> board[i][j];
		}
	}
	queue<Que> Q;
	Q.push({ 0,0,0,0 });
	vis[0][0][0] = true;
	bool success = false;
	
	while (!Q.empty()) {

		auto cur = Q.front();
		Q.pop();
		if (cur.x == h - 1 and cur.y == w - 1) {
			cout << cur.time << endl;
			success = true;
			break;
		}

		if (cur.wcnt < k) {
			for (int i = 0; i < 8; i++) {
				int nx = cur.x + hx[i];
				int ny = cur.y + hy[i];

				if (nx<0 or nx>h - 1 or ny<0 or ny>w - 1)continue;
				if (board[nx][ny] == 0 and vis[nx][ny][cur.wcnt + 1] == false) {
					Q.push({ nx,ny,cur.wcnt + 1,cur.time + 1 });
					vis[nx][ny][cur.wcnt + 1] = true;
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];

			if (nx<0 or nx>h - 1 or ny<0 or ny>w - 1)continue;
			if (board[nx][ny] == 0 and vis[nx][ny][cur.wcnt] == false) {
				Q.push({ nx,ny,cur.wcnt,cur.time + 1 });
				vis[nx][ny][cur.wcnt] = true;
			}
		}
	}
	if (!success) {
		cout << -1 << endl;
	}
}