BFS-1600번 말이 되고픈 원숭이

#include <iostream>
#include <queue>
using namespace std;
const int INF = 987654321;
const int MAX_N = 200;
const int MAX_K = 30;
int visited[MAX_K + 1][MAX_N + 1][MAX_N + 1] = { 0, };
int board[MAX_N + 1][MAX_N + 1];
int N, M;
int jumpY[8] = { -2,-2,-1,-1,1,1,2,2 };
int jumpX[8] = { -1,1,-2,2,-2,2,-1,1 };
int goY[4] = { 1,-1,0,0 };
int goX[4] = { 0,0,1,-1 };

bool can_go(int y, int x)
{
	if (y <1 || y>N || x< 1 || x>M)
		return false;
	if (board[y][x] == 1)
		return false;
	return true;
}

int bfs(int K)
{
	int dist = INF;
	queue <pair<int, pair<int, int>>> q;
	visited[K][1][1] = 1;
	q.push(make_pair(K, make_pair(1, 1)));
	while (!q.empty())
	{
		int nowK = q.front().first;
		int nowY = q.front().second.first, nowX = q.front().second.second;
		q.pop();
		if (nowY == N && nowX == M)
		{
			dist = dist > visited[nowK][nowY][nowX] - 1 ? visited[nowK][nowY][nowX] - 1 : dist;
			continue;
		}
		if (nowK > 0)
		{
			for (int i = 0; i < 8; i++)
			{
				int nextK = nowK - 1;
				int nextY = nowY + jumpY[i] , nextX = nowX + jumpX[i];
				if (can_go(nextY, nextX))
				{
					if (visited[nextK][nextY][nextX])
						continue;
					visited[nextK][nextY][nextX] = visited[nowK][nowY][nowX] + 1;
					q.push(make_pair(nextK, make_pair(nextY, nextX)));
				}
			}
		}
		for (int i = 0; i < 4; i++)
		{
			int nextK = nowK;
			int nextY = nowY + goY[i], nextX = nowX + goX[i];
			if (can_go(nextY, nextX))
			{
				if (visited[nextK][nextY][nextX])
					continue;
				visited[nextK][nextY][nextX] = visited[nowK][nowY][nowX] + 1;
				q.push(make_pair(nextK, make_pair(nextY, nextX)));
			}
		}
	}
	if (dist == INF)
		return -1;
	else
		return dist;
}

int main()
{
	int k;
	cin >> k;
	cin >> M >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> board[i][j];
	cout << bfs(k);

}

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

1600번: 말이 되고픈 원숭이

사실 깔끔한 풀이도 아니었는데 올리는이유는 그냥 한번에 AC를 받아서..😉

벽뚫고 이동하기 문제랑 아이디어는 비슷하다고 생각했다.

visited배열을 3차원 배열로 선언하여 점프를하면 k를 하나줄이고 큐에넣는 방식을 사용했다.

이전 나의풀이와 다른점은 bool isinboard함수랑 벽인지의 유무를 bool can_go함수 하나로 합쳐서 사용한것.

별것 아니지만 사실 형식이 정해져있는 bfs문제에서 자신의 고착화된 코딩패턴은 중요하다고 생각한다.

참, queue <pair<pair<int,int>,pair<int,int>>> 가 참 보기 흉하다고생각해서 다음부턴 역시 구조체 선언해서

푸는게 좋을거같다. 그나저나 한달전에 산1800쪽 짜리 c++책은 언제 다볼수있을까?