백준 1600번 C++

백준 1600번 말이 되고픈 원숭이
https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

정답 코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int K, W, H;
int map[201][201];
int c[201][201][31];

int hx[] = { -2,-1,1,2,2,1,-1,-2 };
int hy[] = { -1,-2,-2,-1,1,2,2,1 };
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };

void Bfs(int s1, int s2, int s3) {
	queue<tuple<int, int,int>> q;
	q.push(make_tuple(s1, s2, s3));
	c[s1][s2][s3] = 1;

	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int jump = get<2>(q.front());
		q.pop();
		if (x == H && y == W) {
			cout << c[x][y][jump] - 1;
			return;
		}
		if (jump < K) {
			for (int i = 0; i < 8; i++) {
				int nx = x + hx[i];
				int	ny = y + hy[i];
				if (nx < 1 || nx > H || ny < 1 || ny > W) continue;
				if(!c[nx][ny][jump+1] && map[nx][ny] == 0) {
					c[nx][ny][jump+1] = c[x][y][jump] + 1;
					q.push(make_tuple(nx, ny, jump + 1));
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > H || ny < 1 || ny > W) continue;
			if (!c[nx][ny][jump] && map[nx][ny] == 0)
			{
				c[nx][ny][jump] = c[x][y][jump] + 1;
				q.push(make_tuple(nx, ny, jump));
			}
		}
	}
	cout << "-1";
	return;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> K >> W >> H;

	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++) cin >> map[i][j];

	Bfs(1, 1, 0);
}

문제 풀이
bfs구현 문제입니다. 가장 먼저 말이 움직일 수 있는 배열과 기본적으로 움직일 수 있는 배열을 각각 만들었습니다.
그리고 동작 횟수를 셀 수 있는 배열을 2차원이 아닌 3차원으로 만들었습니다. K값이 0부터 30까지이기 때문에 2차원을 31개 선언하는 것은 너무 효율성이 떨어진다고 생각하였습니다.
말처럼 움직일 수 있는 횟수가 정해져있기 때문에 jump가 K보다 작을 때는 말처럼 움직일 수 있도록 if문을 추가하였습니다.
나머지 조건들(이미 방문한 곳, 배열의 범위를 벗어난 곳 등)을 continue할 수 있도록 했습니다. 마지막으로 동작 횟수를 셀 수 있도록 c[nx][ny][jump] = c[x][y][jump] + 1;를 선언하였습니다.
bfs문제같은 경우는 코드가 거의 비슷비슷하기 때문에
난이도가 더 낮은 문제들부터 차근차근 풀다 보면 손에 금방 익을 것 같습니다.