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

1600번: 말이 되고픈 원숭이

 

---

1. 문제 요약

정해진 횟수에 한해서 원숭이가 말처럼 움직이며 장애물을 하나 넘어갈 수 있다, 횟수를 모두 소진하면 원숭이처럼만 움직일 수 있다.

이렇게 움직여서 맨 오른쪽 아래에 도착하는 최소한의 이동 횟수를 구하라

 

---

2. 전략

BFS를 사용하며 지금까지 이동한 횟수를 적을 이차원 배열을 사용하면 될 것 같다.

라고 생각하면 큰코다친다. 내가 그랬다.

 

일반적인 이차원 배열로는 해결이 안 됐는데, 그 이유가 횟수가 다 소진될 때까지 말처럼 행동하다가 마지막에 벽을 무조건 넘어야 할 때 못 넘는 현상이 나타나게 된다. (아래 참고)

 

잘못된 상황 ↓↓

무조건 벽을 넘어야 하는 상황 No.1

만약 말로 변할 수 있는 기회가 3번 있다면 원숭이는 이렇게 이동할 것이다.

벽을 넘기도 전에 횟수를 다 써버렸다.

 

문제 해결을 위한 솔루션은 3차원 배열을 만드는 것. 말로만 이해하려 하면 어렵다. 

int dist[201][201][31]

말처럼 행동할때 마다 가장 뒤의 칸을 증가시켜 주는 것이다.

왜 이렇게 해주는 걸까?

 

우리의 원숭이씨는 

여기서 말이 되고 싶을 수도,

때로는 여기서 말처럼 행동하고 싶을 수도 있다.

 

---

3. 코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int k, w, h, board[202][202], dist[202][202][31];
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
int hdx[8] = {-1,-2,-2,-1,1,2,2,1}, hdy[8] = {-2,-1,1,2,2,1,-1,-2};

// x, y, kCnt
queue<tuple<int, int, int>> Q;

// OutOfBounds Check
bool OOB(int x, int y){
  return x < 0 || x >= h || y < 0 || y >= w;
}

int main(){
  init();
  cin >> k >> w >> h;
  for(int i = 0; i < h; ++i)
    for(int j = 0; j < w; ++j)
      cin >> board[i][j];

  memset(dist, -1, sizeof(dist));

  Q.push({0,0,0});
  dist[0][0][0] = 0;
  while(!Q.empty()){
    int x, y, kcnt;
    tie(x, y, kcnt) = Q.front();Q.pop();
    if(kcnt < k){
      for(int dir = 0; dir < 8; ++dir){
        int nx = x+hdx[dir], ny = y+hdy[dir];
        if(OOB(nx, ny))continue;
        if(dist[nx][ny][kcnt+1] >= 0 || board[nx][ny] == 1) continue;
        Q.push({nx, ny, kcnt+1});
        dist[nx][ny][kcnt+1] = dist[x][y][kcnt]+1;
      }
    }
    for(int dir = 0; dir < 4; ++dir){
      int nx = x+dx[dir], ny = y+dy[dir];
      if(OOB(nx, ny))continue;
      if(dist[nx][ny][kcnt] >= 0 || board[nx][ny] == 1) continue;
      Q.push({nx, ny, kcnt});
      dist[nx][ny][kcnt] = dist[x][y][kcnt]+1;
    }
  }

  int min_ans = 2'000'000'000;
  
  for(int l = 0; l <=k; ++l){
    if(dist[h-1][w-1][l] != -1) min_ans = min(min_ans, dist[h-1][w-1][l]);
  }

  if(min_ans == 2'000'000'000) cout << -1;
  else cout << min_ans;
  return 0;
}

말이 될 때마다 kcnt를 증가시켜 주며 bfs를 돌리는 배열을 다르게 해 준다.