백준- 말이되고픈원숭이

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

1600번: 말이 되고픈 원숭이

정답:  일단 3중 for문을 써서 방문하는 맵을 한번더 만들어줘야하네요..

아 이런 아이디어는 어디서 얻어야는건지 ㅋㅋ 처음에 2중for문으로 만들어서 bfs로 풀었는데  풀면 메모리 초과가 납니다.

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

struct Point {
	int x, y, cnt, jump;
};

int main() {
	int K, W, H;
	cin >> K >> W >> H;

	vector<vector<int>> maps(H, vector<int>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> maps[i][j];
		}
	}

	vector<vector<vector<bool>>> visited(H, vector<vector<bool>>(W, vector<bool>(K + 1, false)));

	queue<Point> q;
	q.push({ 0, 0, 0, 0 });
	visited[0][0][0] = true;

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

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;//각 독립적인 현재 횟수 카운트
		int jump = q.front().jump;//말처럼 이동 횟수
		q.pop();

		if (x == W - 1 && y == H - 1) {
			cout << cnt << endl;
			return 0;
		}

		for (int i = 0; i < 12; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int ncnt = cnt + 1;
			int njump = jump;
			if (i >= 4) njump++;//dx, dy가 4이상이면 말처럼 이동 

			if (nx >= 0 && nx < W && ny >= 0 && ny < H && njump <= K && !visited[ny][nx][njump] && maps[ny][nx] == 0) {
				visited[ny][nx][njump] = true;
				q.push({ nx, ny, ncnt, njump });
			}
		}
	}

	cout << -1 << endl;
	return 0;
}

 

이건 초반에 2중 for문으로 해결하려던 방법입니다.

정답은 올바른데 메모리 초과가 납니다 ㅠ ㅎ 

#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
using namespace std;

void Prints(vector<vector<int>>maps, int r,int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
struct Data {
	int w;
	int h;
	int count;
	vector<vector<int>>maps;
	int movingCount=0;
};

int main() {
	int k;
	int w ;
	int h;
	cin >> k >> w >> h;

	vector<vector<int>> maps;
	for (int i = 0; i < h; i++) {
		vector<int>tmpMap;
		for (int j = 0; j < w; j++) {
			int tmp;
			cin >> tmp;
			tmpMap.push_back(tmp);
		}
		maps.push_back(tmpMap);
	}
	int movingCount = 0;
	queue<Data>q;
	Data d;
	d.w = 0;
	d.h = 0;
	d.count = 0;
	maps[0][0] = 1;
	d.maps = maps;
	d.movingCount = movingCount;
	q.push(d);
	
	int dirW[4] = {0,0,1,-1};
	int dirH[4] = {1,-1,0,0};
	int kight[2] = { 1,-1 };
	int dirKnightW[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };
	int dirKnightH[8] = { 2, 2, -2, -2, 1, 1, -1, -1 };

	int answer=-1;
	bool bFinish = false;
	while (!q.empty()) {
		Data start=q.front();
		q.pop();
		if (bFinish == true) {
			break;
		}

		if (start.movingCount < k) {
			//나이트 움직임
			bool bKnight = false;
			for (int i = 0; i < 8; i++) {
				int tmpDirW = start.w + dirKnightW[i];
				int tmpDirH = start.h + dirKnightH[i];
				 if (tmpDirW <= -1 || tmpDirH <= -1 || tmpDirW >= w || tmpDirH >= h) {
					 continue;
				 }
				 if (start.maps[tmpDirH][tmpDirW] == 0) {
					 bKnight = true;
					 start.maps[tmpDirH][tmpDirW] = 1;
					 Data tmpd;
					 tmpd.w = tmpDirW;
					 tmpd.h = tmpDirH;
					 tmpd.count = start.count + 1;
					 tmpd.maps = start.maps;
				
					 tmpd.movingCount = start.movingCount + 1;

					 q.push(tmpd);
		
					 start.maps[tmpDirH][tmpDirW] = 0;
					
					 if (tmpDirW == w - 1 && tmpDirH == h - 1) {
						 answer = tmpd.count;
						 bFinish = true;
						
					 }
				 }
			}

				for (int i = 0; i < 4; i++) {
					int tmpDirW = start.w + dirW[i];
					int tmpDirH = start.h + dirH[i];
					if (tmpDirW <= -1 || tmpDirH <= -1 || tmpDirW >= w || tmpDirH >= h) {
						continue;
					}

					if (start.maps[tmpDirH][tmpDirW] == 0) {
						start.maps[tmpDirH][tmpDirW] = 1;
						Data tmpd;
						tmpd.w = tmpDirW;
						tmpd.h = tmpDirH;
					
						tmpd.count = start.count + 1;
						tmpd.maps = start.maps;
					
						tmpd.movingCount = start.movingCount;
	
						q.push(tmpd);
						
						start.maps[tmpDirH][tmpDirW] = 0;
						
						if (tmpDirW == w - 1 && tmpDirH == h - 1) {
							answer = tmpd.count;
							bFinish = true;
						
						}

					}
				}
			
		}
		//좌우상하
		else  {
			for (int i = 0; i < 4; i++) {
				int tmpDirW = start.w + dirW[i];
				int tmpDirH = start.h + dirH[i];
				if (tmpDirW <= -1 || tmpDirH <= -1 || tmpDirW >= w || tmpDirH >= h) {
					continue;
				}

				if (start.maps[tmpDirH][tmpDirW] == 0) {
			
					start.maps[tmpDirH][tmpDirW] = 1;
					Data tmpd;
					tmpd.w = tmpDirW;
					tmpd.h = tmpDirH;
					tmpd.count = start.count + 1;
					tmpd.maps = start.maps;
					tmpd.movingCount = start.movingCount;
					q.push(tmpd);
					start.maps[tmpDirH][tmpDirW] = 0;
					if (tmpDirW == w - 1 && tmpDirH == h - 1) {
						answer = tmpd.count;
						bFinish = true;
					}
				}
			}
		}
	}
	cout << answer;
	return 0;