1. 문제설명

말은 체스의 나이트와 같이 2칸 직선방향, 한칸 대각선 방향을 움직일 수 있다.
- 특히 도착지점을 제외하면 건너뛸 수 있다.
원숭이는 상하좌우 1칸씩 이동가능하다.
원숭이는 말처럼 움직일 수 있는 능력이 k번 주어진다.
그냥 이동하든, 능력을 사용하든 한번의 동작으로 친다.
원숭이가 (0,0)에서 (w-1, h-1)까지 동작의 최솟값을 구하라.
- 도착할 수 없으면 -1을 출력한다.

2. 알고리즘 설계

일반적인 bfs와 같이 상,하,좌,우 한칸씩 움직이는 for-loop
나이트와 같이 움직이는 for-loop

단 k의 횟수가 남아있는 동안만 나이트의 for-loop를 실행해야 한다.

	if (cur.k < k) {
      for (int dir = 0; dir < 8; dir++) {
          int ny = cur.y + move_ky[dir];
          int nx = cur.x + move_kx[dir];

          if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
          if (visited[ny][nx][cur.k + 1] || arr[ny][nx] == 1) continue;

          q.push({ ny, nx, cur.d + 1, cur.k + 1 });
          visited[ny][nx][cur.k + 1] = true;
      }
  }

  for (int dir = 0; dir < 4; dir++) {
      int ny = cur.y + dy[dir];
      int nx = cur.x + dx[dir];

      if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
      if (visited[ny][nx][cur.k] || arr[ny][nx] == 1) continue;

      q.push({ ny, nx, cur.d + 1, cur.k });
      visited[ny][nx][cur.k] = true;
  }

3. 로직

탐색 조건은 현재 x, y가 끝에 도달했을 때 weight를 반환하면 된다.
- 큐가 비어도 찾지 못하면 -1을 반환한다.
여기서 체크해야할 건, 다음 두 경우 중 어떤 게 더 나은 선택인가이다.
- 나이트의 움직임을 사용해서 (x,y)를 갔을 때,
- 원숭이의 움직임을 사용해서 (x,y)를 갔을 때
따라서 정답을 바로 만나면 탈출해버리는 일반 BFS 방식으로 구현하면 안된다.
- 최적의 해가 큐에 남아있을 수도 있기 때문이다.
k의 값은 최대 30이다. 즉, 30번의 능력을 사용할 수 있다.
- bool visited[200][200][31];
- 능력을 사용했을 때, 사용하지 않았을 때를 각각 방문했는지 체크하면 된다!

4. 전체 코드

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

typedef struct {
	int y, x, d, k;
}Pos;

const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
const int move_ky[] = { 1,2,2,1,-1,-2,-2,-1 };
const int move_kx[] = { -2,-1,1,2,2,1,-1,-2 };

int k, w, h;
int arr[200][200];
bool visited[200][200][31];

int bfs() {
	queue<Pos> q;
	q.push({ 0,0,0 });
	visited[0][0][0] = true;

	while (!q.empty()) {
		Pos cur = q.front();
		q.pop();

		if (cur.y == h - 1 && cur.x == w - 1) return cur.d;

		if (cur.k < k) {
			for (int dir = 0; dir < 8; dir++) {
				int ny = cur.y + move_ky[dir];
				int nx = cur.x + move_kx[dir];

				if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
				if (visited[ny][nx][cur.k + 1] || arr[ny][nx] == 1) continue;

				q.push({ ny, nx, cur.d + 1, cur.k + 1 });
				visited[ny][nx][cur.k + 1] = true;
			}
		}

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.y + dy[dir];
			int nx = cur.x + dx[dir];

			if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
			if (visited[ny][nx][cur.k] || arr[ny][nx] == 1) continue;

			q.push({ ny, nx, cur.d + 1, cur.k });
			visited[ny][nx][cur.k] = true;
		}
	}

	return -1;
}

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

	cin >> k >> w >> h;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> arr[i][j];

	cout << bfs();
	return 0;
}

BOJ 1600. 말이 되고픈 원숭이

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드