BOJ : 1600 말이 되고픈 원숭이

입력

첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

출력

첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

 

---

[BOJ 1600(G5) 리뷰]

푸느라 혈압올랐던 문제.. 

일단 첨에 문제 잘못이해하고 삽질 1시간

메모리 초과나서 +1시간

100%에서 틀렸다고 나와서 +1시간..

거의 3시간이 걸렸고 결국 경계조건에 대해 예외처리를 해주고나서야 정답처리가 되었다.

 

첨엔 설명만 읽고 겁나쉽네? 하고 풀었지만 은근 문제조건이 까다로웠다.

첨엔 무조건 스킬많이쓸수록 빨리갈수있는거아냐? 하고 생각했지만 벽으로 막혀있어서 스킬이 못쓰는 경우가 있고

스킬을 다 안쓰더라도 목적지에 도착할 수 있는경우가 있기때문에 이런것들을 다 생각해줘야한다.

결국 스킬을 쓸때마다 새로운 배열에 기록하는 방법을 택했다.

그리하여 만약 스킬을 7번을 사용했다면 총 7개의 보드판에 기록이되어 그중 최소값을 출력하면 된다.

 

아직까지 이런식으로 3D배열을 응용하는 문제는 정말 어렵다.. 더 열심히 공부해야겠다.

 

---

 

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

#define X first
#define Y second

int board[201][201];
int vis[201][201][31]; 
int Hdx[8] = { 1,1,-1,-1,2,2,-2,-2 }; //말의 이동
int Hdy[8] = { 2,-2,2,-2,1,-1,1,-1 };
int Mdx[4] = {1,0,-1,0}; //원숭이 이동
int Mdy[4] = {0,1,0,-1};

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	int K;
	cin >> K;
	int W, H;
	cin >> H >> W;
	for (int i = 0; i < W; i++)
	{
		for (int j = 0; j < H; j++)
		{
			cin >> board[i][j];
		}
	}

	if (board[0][0] == 1)
	{
		cout << -1;
		return 0;
	}
	queue <pair<pair<int, int>, int>> Q;

	Q.push({{ 0,0 },K });
	vis[0][0][K] = 1; //K부터 시작하여 스킬사용할때마다 K-1배열에 저장
	while (!Q.empty())
	{
		auto cur = Q.front();
		Q.pop();
		int curx = cur.first.X;
		int cury = cur.first.Y;
		int skill = cur.second;
		if (curx == W - 1 && cury == H - 1)
		{
			cout << vis[curx][cury][skill]-1;
			return 0;
		}

		if (skill) {
			for (int dir = 0; dir < 8; dir++)
			{
				int nx = curx + Hdx[dir];
				int ny = cury + Hdy[dir];
				if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
				if (vis[nx][ny][skill]!=0 || vis[nx][ny][skill-1] != 0 || board[nx][ny] != 0 ) continue;
				vis[curx][cury][skill - 1] = vis[curx][cury][skill];
				vis[nx][ny][skill - 1] = vis[curx][cury][skill-1] + 1;
				Q.push({ { nx,ny }, skill - 1 });
				if (nx == W - 1 && ny == H - 1)
				{
					cout << vis[nx][ny][skill-1] - 1;
					return 0;
				}
			}

		}

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = curx + Mdx[dir];
			int ny = cury + Mdy[dir];
			if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
			if (vis[nx][ny][skill] != 0 || board[nx][ny] != 0) continue;
			vis[nx][ny][skill] = vis[curx][cury][skill] + 1;
			Q.push({ { nx,ny },skill });
			if (nx == W - 1 && ny == H - 1)
			{
				cout << vis[nx][ny][skill] - 1;
				return 0;
			}
		}
	}

	cout << -1;

}

 

 

빡침.JPG