[BOJ/1600/C++] 말이 되고픈 원숭이

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

문제

• 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다.
• 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.
• 이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다.
• 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.

조건

• 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다.
• 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

풀이

생각의 허점을 파고들기 좋은 문제이다. 실제로 , 한번 틀렸다.
단순하게 말처럼 움직이는게 먼 거리를 간다고 해서, 말을 먼저 이동시켜주게 되면 안된다!! 왜냐하면, 무조건 골인지점에 갈 수 있는건 아니기 때문이다. 아래의 반례를 보자.

1
4 4
0 0 0 0
1 0 0 0
0 0 1 1
0 1 0 0

(0,0) -> (0,1) -> (1,1) -> (2,1) -> (3,3)으로 나중에 말처럼 이동해야 골인지점에 도달 할 수 있다.

즉, 방문한 점이라고 해도, 해당 방문한 점이 진짜 최소거리인지 아닌지 모르게 된다. 이럴때 이용할수 있는 방법은 , 값을 하나 더 추가하여 3차원 방문배열을 만드는 것이다.
점프한 횟수만큼 추가로 방문배열을 만들어서 , 점프한 횟수에 따라서 방문배열이 따로 있게되면 같은 점을 방문하더라도 BFS는 최단거리로 점을 방문하기 때문에, 목표점을 먼저 도달할 수 있게 된다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

struct Point
{
  int x;
  int y;
  int dist;
  int jump;
};

int N, M, K;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int horseX[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
int horseY[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int board[201][201];
bool visited[201][201][31];

bool outOfRange(int x, int y)
{
  return (x < 0 || x >= N || y < 0 || y >= M);
}

void bfs(int start_x, int start_y)
{
  queue<Point> Q;
  for (int i = 0; i <= K; i++)
  {
    visited[start_x][start_y][i] = true;
  }
  Q.push({start_x, start_y, 0, 0});

  while (!Q.empty())
  {
    Point cur = Q.front();
    Q.pop();
    if (cur.x == N - 1 && cur.y == M - 1)
    {
      cout << cur.dist << '\n';
      return;
    }
    // 점프 횟수가 남아 있다면 , 먼저 이동하는게 이득일까??
    // 그건 모른다.
    if (cur.jump < K)
    {
      for (int dir = 0; dir < 8; dir++)
      {
        int nx = cur.x + horseX[dir];
        int ny = cur.y + horseY[dir];
        if (outOfRange(nx, ny))
          continue;
        // 점프를 해서 방문 했거나, 벽을 뛰어넘을 수는 있찌만, 도착하는 지점이 벽이면 안된다.
        if (visited[nx][ny][cur.jump + 1] || board[nx][ny] == 1)
          continue;
        visited[nx][ny][cur.jump + 1] = true;
        Q.push({nx, ny, cur.dist + 1, cur.jump + 1});
      }
    }
    // 그냥 갈 수도 있다.
    for (int dir = 0; dir < 4; dir++)
    {
      int nx = cur.x + dx[dir];
      int ny = cur.y + dy[dir];
      if (outOfRange(nx, ny))
        continue;
      if (visited[nx][ny][cur.jump] || board[nx][ny] == 1)
        continue;
      visited[nx][ny][cur.jump] = true;
      Q.push({nx, ny, cur.dist + 1, cur.jump});
    }
  }
  cout << -1 << '\n';
  return;
}

int main()
{
  fastio;
  cin >> K;
  cin >> M >> N;

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < M; j++)
    {
      cin >> board[i][j];
    }
  }
  bfs(0, 0);
  return 0;
}