[백준/BOJ] 백준 1600번 : 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

현재 위치에서 말처럼 움직일 수 있는 횟수가 남았으면 말처럼 움직일 수 있는 방법과, 인접한 칸으로 움직일 수 있는 방법이 있고, 말처럼 움직일 수 있는 횟수가 없으면 인접한 칸으로 움직일 수 있는 방법뿐이다.

 

코드

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

int w, h;
int dx_dy1[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int dx_dy2[8][2] = { {-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };
int board[200][200];
int discoverd[200][200][31];
int depth[200][200][31];

void pre()
{
	for (int i = 0; i < 200; i++)
		for (int j = 0; j < 200; j++)
			for (int k = 0; k < 31; k++)
				discoverd[i][j][k] = 0;
}

//start는 시작지점과 k의 정보를 가지고 있다
int Solve(pair<pair<int, int>, int> start)
{
	pre();

	discoverd[start.first.first][start.first.second][start.second] = 1;
	depth[start.first.first][start.first.second][start.second] = 0;

	queue<pair<pair<int, int>, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<pair<int, int>, int> here = q.front();
		q.pop();

		//맨 오른쪽 아래에 도착했을때
		if (here.first.first == h - 1 && here.first.second == w - 1)
			return depth[here.first.first][here.first.second][here.second];

		//말 처럼 움직일수 있는 횟수가 남았을때
		if (here.second > 0)
		{
			for (int i = 0; i < 8; i++)
			{
				pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dx_dy2[i][0], here.first.second + dx_dy2[i][1]), here.second - 1);

				if (there.first.first >= 0 && there.first.first < h && there.first.second >= 0 && there.first.second < w && board[there.first.first][there.first.second] == 0 && discoverd[there.first.first][there.first.second][there.second] == 0)
				{
					discoverd[there.first.first][there.first.second][there.second] = 1;
					depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;
					q.push(there);
				}

			}
		}

		//인접한칸으로 움직을때
		for (int i = 0; i < 4; i++)
		{
			pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dx_dy1[i][0], here.first.second + dx_dy1[i][1]), here.second);

			if (there.first.first >= 0 && there.first.first < h && there.first.second >= 0 && there.first.second < w && board[there.first.first][there.first.second] == 0 && discoverd[there.first.first][there.first.second][there.second] == 0)
			{
				discoverd[there.first.first][there.first.second][there.second] = 1;
				depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;
				q.push(there);
			}
		}
	}

	//맨 오른쪽 아래에 도착할 수 없을때
	return -1;
}

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

	int k;
	int temp;

	cin >> k;
	cin >> w >> h;

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

	pair<pair<int, int>, int> start = make_pair(make_pair(0, 0), k);

	cout << Solve(start);

	return 0;
}