본문 바로가기
알고리즘 문제풀이/백준

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

by m2162003 2020. 10. 29.

www.acmicpc.net/problem/1600

 

1600번: 말이 되고픈 원숭이

첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있

www.acmicpc.net

 

- 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;
}

 

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 13913] 숨바꼭질 4  (0) 2020.11.01
[백준 13549] 숨바꼭질3  (0) 2020.10.29
[백준 6593] 상범빌딩  (0) 2020.10.28
[백준 7569] 토마토  (0) 2020.10.27
[백준 11725] 트리의 부모 찾기  (0) 2020.10.04

댓글