[BOJ] 1600_말이 되고픈 원숭이 with cpp

# 생각

조건에 맞춰 나이트의 이동 bfs와 인접한 칸으로만 움직이는 bfs 두가지를 돌리면 된다

 

단, k번 만큼만 나이트 이동을 할 수 있기 때문에 vis배열을 3차원으로 선언하여

나이트 이동일 때와 인접한 칸 이동일 때의 배열을 분리해서 관리해주면 해결 가능하다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
bool OOB(int x, int y, int n, int m) { return x < 0 or x >= n or y < 0 or y >= m; }
void fastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); }

const int ddx[] = { 1,2,2,1,-1,-2,-2,-1 }, ddy[] = { 2,1,-1,-2,-2,-1,1,2 };
int graph[222][222], vis[222][222][33];
queue<tuple<int, int, int, int>> q;

int main()
{
	fastIO();
	int k, w, h;
	cin >> k >> w >> h;
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> graph[i][j];
		}
	}

	vis[0][0][0] = 1;
	q.push({ 0,0,0,0 });
	while (!q.empty())
	{
		int x, y, cnt, ans;
		tie(x, y, cnt, ans) = q.front(); q.pop();
		if (x == h - 1 and y == w - 1)
		{
			cout << ans;
			return 0;
		}
		if (cnt < k)
		{
			for (int dir = 0; dir < 8; dir++)
			{
				int nx = x + ddx[dir], ny = y + ddy[dir];
				if (OOB(nx, ny, h, w) or graph[nx][ny] == 1 or vis[nx][ny][cnt + 1] == 1) continue;
				vis[nx][ny][cnt + 1] = 1;
				q.push({ nx,ny,cnt + 1,ans + 1 });
			}
		}
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = x + dx[dir], ny = y + dy[dir];
			if (OOB(nx, ny, h, w) or graph[nx][ny] == 1 or vis[nx][ny][cnt] == 1) continue;
			vis[nx][ny][cnt] = 1;
			q.push({ nx,ny,cnt,ans + 1 });
		}
	}
	cout << -1;
}

 

---

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

1600번: 말이 되고픈 원숭이