[백준 1600] 말이 되고픈 원숭이

풀이

기초적인 BFS 알고리즘을 잘한다고 알았던 내가, 이 문제를 보고 한 동안 머리가 아펐다.

기존 BFS 알고리즘 문제들은 대부분 2차원 배열 안에서 해결할 수 있었지만, 이 문제에서는 그 프레임을 벗어나야 해결할 수 있는 문제였다.

 

원숭이는 기본적으로 상,하,좌,우로 이동할 수 있지만,

이 원숭이는 특별해서 K번의 말의 능력을 사용해서 마치 나이트처럼 움직일 수 있다.

즉, 기존 원숭이처럼 움직이되 어떠한 경우에서는 말의 능력을 이용하면 더 빨리 도착할 수 있다는 것이다.

 

핵심은 바로 방문 배열을 3차원 배열로 만드는 것이다.

vis[x][y][k] : (x,y)를 k번의 능력을 사용해서 도달했는지 여부를 체크하는 방문 배열이다.

무슨 말이냐면,

 

(4,5)를 온 경우를 생각해보자.

(4,5)라는 지점을 원숭이가 그냥 능력을 사용하지 않아서 온 경우도 있을 것이다.

이 때는 능력을 사용하지 않았기 때문에 능력의 사용 횟수는 똑같다.

 

(4,5)라는 지점을 원숭이가 말의 능력을 사용해서 온 경우도 있다는 것이다.

이 때는 능력을 사용했기 때문에 이전에 k번의 능력을 사용해서 왔다면

지금은 (4,5)를 밟기 위해서 k + 1번의 능력을 사용해서 온 경우가 된다.

 

최단 경로는 누가 더 빨리 와서 그 고지점을 먼저 밟냐 안 밟냐에 따라 승부가 갈리기 때문에

먼저 들어온 녀석이 방문 배열을 true로 만들게 된다.

 

나머지는 기존 BFS 알고리즘처럼 짜면 풀 수 있게 된다.

 

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

int mx[] = { 0,0,1,-1 };
int my[] = { 1,-1,0,0 };
int hx[] = { -1,-2,-2,-1,1,2,2,1 };
int hy[] = { -2,-1,1,2,-2,-1,1,2 };

int w, h, k;
int board[201][201];
bool vis[201][201][31]; // vis[x][y][k] : (x,y)지점에 능력을 k번 사용해서 왔습니다.

struct Monkey
{
	int x;
	int y;
	int cost;
	int used;
};

int bfs()
{
	queue<Monkey> q;
	q.push({ 0,0,0,0 });
	vis[0][0][0] = true;
	while (!q.empty())
	{
		Monkey m = q.front();
		q.pop();

		if (m.x == h - 1 && m.y == w - 1) return m.cost;

		// 말의 능력을 사용할 수 있다면
		if (m.used < k)
		{
			for (int i = 0; i < 8; ++i)
			{
				int nx = m.x + hx[i];
				int ny = m.y + hy[i];
				if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
				if (board[nx][ny] == 0 && !vis[nx][ny][m.used + 1])
				{
					vis[nx][ny][m.used + 1] = true;
					q.push({ nx,ny,m.cost + 1, m.used + 1 });
				}
			}
		}

		for (int i = 0; i < 4; ++i)
		{
			int nx = m.x + mx[i];
			int ny = m.y + my[i];
			if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
			if (board[nx][ny] == 0 && !vis[nx][ny][m.used])
			{
				vis[nx][ny][m.used] = true;
				q.push({ nx,ny,m.cost + 1, m.used });
			}
		}
	}

	return -1;
}

int main()
{
	freopen("input.txt", "r", stdin);

	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> k >> w >> h;
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			cin >> board[i][j];
		}
	}

	cout << bfs() << '\n';
	return 0;
}