BaekJoon 1600번: 말이 되고픈 원숭이(C++)

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

1600번: 말이 되고픈 원숭이

풀이법

1) BFS를 활용하는 문제이며, 문제에서 주어진 w,h 값이 정확히 무엇인지를 먼저 확인하는 것이 중요하다

2) 체스의 knight 처럼 움직일 수 있는 배열과, 상하 좌우로 움직일 수 있는 배열을 따로 만들어 주었다.

int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int bx[8] = {-1,-2,-2,-1,1,2,2,1};
int by[8] = {-2,-1,1,2,2,1,-1,-2 };

v 배열은 상하좌우로, b 배열은 knight처럼 움직이는 것을 뜻한다.

3) visited 배열은 3차원으로 선언하였다. 2차원 배열로 문제를 해결하려하면 답을 찾을 수 없다.

한번 방문 한 자리는 k가 얼마 일때 방문한 자리인지 꼭 확인해야 문제를 해결할 수 있었다.

		if (nowK < k)
		{
			for (int i = 0; i < 8; i++)
			{
				int nextX = nowX + bx[i];
				int nextY = nowY + by[i];
				if (nextX < 0 || nextY < 0 || nextX >= w || nextY >= h)
					continue;
				if(!visited[nextX][nextY][nowK+1] && arr[nextX][nextY]==0)
				{
					visited[nextX][nextY][nowK+1] = true;
					q.push({ nextX,{nextY,{cnt + 1,nowK + 1}} });
				}
	
			}
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= w || nextY >= h)
				continue;
			if (!visited[nextX][nextY][nowK] && arr[nextX][nextY]== 0)
			{
				visited[nextX][nextY][nowK] = true;
				q.push({ nextX,{nextY,{cnt + 1,nowK}} });
			}

		}

visited[nextX][nextY][nowK]에서 nowK부분이 필수적인 영역이다.

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <set>
using namespace std;

int k;
int w, h;
int arr[201][201];
bool visited[201][201][31];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int bx[8] = {-1,-2,-2,-1,1,2,2,1};
int by[8] = {-2,-1,1,2,2,1,-1,-2 };
void bfs()
{
	queue < pair<int, pair<int,pair< int,int>>>> q;
	visited[0][0][0] = true;
	q.push({ 0,{0,{0,0}}});
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int cnt = q.front().second.second.first;
		int nowK = q.front().second.second.second;
		q.pop();
		if (nowX == w - 1 && nowY == h - 1 && arr[nowX][nowY]==0)
		{
			cout << cnt;
			return;
		}
		if (nowK < k)
		{
			for (int i = 0; i < 8; i++)
			{
				int nextX = nowX + bx[i];
				int nextY = nowY + by[i];
				if (nextX < 0 || nextY < 0 || nextX >= w || nextY >= h)
					continue;
				if(!visited[nextX][nextY][nowK+1] && arr[nextX][nextY]==0)
				{
					visited[nextX][nextY][nowK+1] = true;
					q.push({ nextX,{nextY,{cnt + 1,nowK + 1}} });
				}
	
			}
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= w || nextY >= h)
				continue;
			if (!visited[nextX][nextY][nowK] && arr[nextX][nextY]== 0)
			{
				visited[nextX][nextY][nowK] = true;
				q.push({ nextX,{nextY,{cnt + 1,nowK}} });
			}

		}

	}
	cout << -1;
	return;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> k;
	cin >> h >> w;
	for (int i = 0; i < w; i++)
	{
		for (int j = 0; j < h; j++)
			cin >> arr[i][j];
	}
	bfs();
}