[C/C++] 백준 1600번 - 말이 되고픈 원숭이

 

 

<코드>

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

int K, W, H, x;
int map[201][201];
int dx[12] = { 1,-1,0,0,-1,-2,-2,-1,1,2,2,1 };
int dy[12] = { 0,0,1,-1,-2,-1,1,2,2,1,-1,-2 };
bool visit[201][201][31];
queue<tuple<int, int, int, int>> q; // x,y,움직인 횟수,남은 점프 횟수

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie();

	cin >> K;
	cin >> W >> H;

	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			cin >> x;

			// 장애물이라면
			if (x == 1) map[i][j] = -1;
		}
	}

	q.push({ 1,1,0,K });
	visit[1][1][0] = true;

	while (!q.empty())
	{
		int now_x = get<0>(q.front());
		int now_y = get<1>(q.front());
		int cnt = get<2>(q.front());
		int jump = get<3>(q.front());
		q.pop();

		if (now_x == H && now_y == W)
		{
			cout << cnt << '\n';
			return 0;
		}

		for (int i = 0; i < 12; i++)
		{
			int next_x = now_x + dx[i];
			int next_y = now_y + dy[i];

			// 범위에서 벗어난다면 pass
			if (next_x <= 0 || next_x > H || next_y <= 0 || next_y > W)
				continue;

			if (i >= 4) // 점프이동
			{
				if (jump == 0) continue; // 점프사용 가능횟수가 0이라면 패스
				if (!visit[next_x][next_y][jump - 1] && map[next_x][next_y] != -1)
				{
					q.push({ next_x,next_y,cnt + 1,jump - 1 });
					visit[next_x][next_y][jump - 1] = true;
				}
			}
			else // 인접한 칸으로 이동
			{
				if (!visit[next_x][next_y][jump] && map[next_x][next_y] != -1)
				{
					q.push({ next_x,next_y,cnt + 1,jump });
					visit[next_x][next_y][jump] = true;
				}
			}
		}

	}

	cout << -1 << '\n';

}

 

 

 

 

 

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이