(C++) [백준 1600번] 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

체스의 나이트와 같은 이동방식을 가지는 말이 있고(말은 장애물을 뛰어넘을 수 있음) 상하좌우 1칸씩 이동할 수 있는

원숭이가 있다. 원숭이는 원래는 상하좌우 1칸씩만 움직일 수 있지만 k번만큼 말처럼 이동할 수 있다.

이 때, (0,0)에서 (h-1,w-1) [w,h의 위치가 반대임을 주의] 까지의 최단경로를 구하는 문제이다.

 

내가 생각한 방법은 다음과 같다.

1. 최대 k번 말처럼 움직일 수 있다고 했으므로 3차원 배열을 사용하여 거리를 구한다. 0번 인덱스는 말처럼 0번 움직였을 때, 1번 인덱스는 1번... k번 인덱스는 k번 움직였을 때의 최단경로이다.

2. 큐에서 한 점을 빼서 원숭이처럼 이동하는 경우, 말처럼 이동하는 경우 각각에 대해 BFS를 한다.

3. 2번에서 뺀 점이 (h-1,w-1)일 경우 해당 인덱스의 값을 리턴한다.

 

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
#define MAX 202
#define MMAX 32
#define X first
#define Y second
int board[MAX][MAX];
int dist[MAX][MAX][MMAX];
bool vis[MAX][MAX][MMAX];
int k, w, h;
int hdx[8] = { 2,1,-1,-2,-2,-1,1,2 };
int hdy[8] = { 1,2,2,1,-1,-2,-2,-1 };
int mdx[4] = { 1,0,-1,0 };
int mdy[4] = { 0,1,0,-1 };
queue <tuple <int, int, int>> q;
bool OOB(int x, int y)
{
	if (x < 0 || y < 0 || x >= w || y >= h) return true;
	return false;
}
void input()
{
	cin >> k >> h >> w;
	for (int i = 0; i < w; i++)
	{
		for (int j = 0; j < h; j++)
			cin >> board[i][j];
	}
}
int solve()
{
	if (w == 1 && h == 1) return 0;
	q.push({ 0,0,0 });
	vis[0][0][0] = true;
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		int x, y, horse;
		tie(x, y, horse) = cur;
		if (x == w - 1 && y == h - 1)
		{
			return dist[x][y][horse];
		}

		if (horse < k)
		{
			for (int dir = 0; dir < 8; dir++) // 말 이동
			{
				int nx = x + hdx[dir];
				int ny = y + hdy[dir];
				if (OOB(nx, ny) || board[nx][ny] == 1) continue;

					if (!vis[nx][ny][horse+1]) // 아직 방문하지 않았으면
					{
						dist[nx][ny][horse + 1] = dist[x][y][horse] + 1; // 말 1턴 쓰고 1칸 전진
						q.push({ nx,ny,horse + 1 });
						vis[nx][ny][horse + 1] = true;
					}
				
			}
		}

		for (int dir = 0; dir < 4; dir++) // 원숭이 이동
		{
			int nx = x + mdx[dir];
			int ny = y + mdy[dir];
			if (OOB(nx, ny) || board[nx][ny] == 1) continue;
			
				
				if (!vis[nx][ny][horse]) // 아직 방문하지 않았으면
				{
					dist[nx][ny][horse] = dist[x][y][horse] + 1; // 1칸 전진
					q.push({ nx,ny,horse });
					vis[nx][ny][horse] = true;
				}
			
		}
	}
	return -1;
}
int main()
{
	cin.tie(); ios::sync_with_stdio(0);
	input(); cout << solve();
}