[백준 1600] 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

- 3차원 배열 bfs문제였다.

- 처음엔 2차원 배열로 했다가 틀렸다. 3차원으로 해야 하는 이유는 말을 통해서 가는 거리와 원숭이가 가는 거리를 분리해줘야 하기 때문이다.

말을 이용해서는 목적지까지 도착을 못한다고 가정해보자. (원숭이만을 이용해서 갈 수 있다고 가정) 2차원 배열에 path를 등록하여 이미 지나간 거리를 지나가지 않는다면 도착지까지 도달하지 못할 것이다. 그래서 말을 사용했을 때 path를 분리해주어야 한다.

반례: 

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0

 

정답은 6이지만 처음 짠 코드에선 -1이 나왔다.

 

정답:

#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX 201

using namespace std;

int k, w, h;
int monkey[MAX][MAX];
int path[30][MAX][MAX];

struct Move
{
  int x, y, horse;
};

int kx[8] = {2, 1, 2, 1, -2, -1, -2, -1};
int ky[8] = {1, 2, -1, -2, 1, 2, -1, -2};

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

bool isValid(int row, int col)
{
  if (row < 0 || col < 0 || row > h - 1 || col > w - 1)
  {
    return false;
  }
  return true;
}

int main(void)
{
  scanf("%d%d%d", &k, &w, &h);

  queue<Move> q;
  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      scanf("%d", &monkey[i][j]);
    }
  }

  q.push({0, 0, k});
  memset(path, 0, sizeof(path));

  while (!q.empty())
  {
    Move fr = q.front();
    q.pop();

    if (fr.x == w - 1 && fr.y == h - 1)
    {
      printf("%d\n", path[fr.horse][fr.y][fr.x]);
      return 0;
    }

    if (fr.horse > 0)
    {
      for (int i = 0; i < 8; i++)
      {
        int nX = fr.x + kx[i];
        int nY = fr.y + ky[i];

        if (isValid(nY, nX) && !monkey[nY][nX] && !path[fr.horse - 1][nY][nX])
        {
          path[fr.horse - 1][nY][nX] = path[fr.horse][fr.y][fr.x] + 1;
          q.push({nX, nY, fr.horse - 1});
        }
      }
    }

    for (int i = 0; i < 4; i++)
    {
      int nX = fr.x + dx[i];
      int nY = fr.y + dy[i];

      if (isValid(nY, nX) && !monkey[nY][nX] && !path[fr.horse][nY][nX])
      {
        path[fr.horse][nY][nX] = path[fr.horse][fr.y][fr.x] + 1;
        q.push({nX, nY, fr.horse});
      }
    }
  }

  printf("-1\n");
  return 0;
}