[BOJ 1600번] 말이 되고픈 원숭이

BFS 문제는 일반적으로 기본문제만 풀수있는 수준과 심화 문제를 풀수있는 수준이 극명하게 갈리는데

이 문제는 바로 그 경계선이 되는 수준의 문제인것 같다. 정답률이 20퍼다. 

본인이 번뜩이는 창의성이 부족한 평범한 사람이라면

분명히 이 문제에서 막히게 될것이고 이것은 발상의 비약이 필요한 순간이라고 할수 있다.  물론 내 이야기다.

알고리즘을 풀면서 어떻게 이런 생각을 하는지 감탄을 넘어서 존경하게되는 순간과 희열을 느끼는 순간과 벽을 느끼는 순간이 종종 있는데 이 문제도 그런류의 문제인것 같다.

나 역시 이문제를 좀 고민해보고 답지를 본 입장으로서 새로운 발상에 눈을 뜬 기분이였다.

 

일단 딱봐도 BFS를 발상하는것은 어렵지 않다.

문제는 원숭이는 말처럼 움직이는 횟수가 최대 K번이기 때문에 일반적인 BFS처럼 짜면 안된다는 것이다.

횟수만 제한되지 않았다면 훨씬 쉬웠을 것이다.

 

원숭이가 말처럼 움직이는 횟수는 0~K번 까지 모든 경우를 해볼수 있어야 하기 때문에 백트래킹을 고려해보았지만

K가 최대 30이기 때문에 불가능했고 답지를 보고 새로운 발상을 배웠다.

 

말처럼 움직이는 횟수가 0일때 1일때 ... K일때 까지 다차원으로 생각을 해야한다. 즉 차원을 넘나 들어야 한다.

int board[205][205];

int dist[32][205][205];

그래서 거리를 저장하는 배열은 3차원이 돼야한다.

 

그럼 어떻게 말처럼 움직이는 횟수가 0부터 K번까지 모든 경우가 큐에 들어 갈수 있을까?

 

while (!q.empty())

{

int a,x,y;

tie(a,x,y) = q.front(); q.pop();

if(a < k){

for(int dir=0; dir<8; dir++){

int nx = x + hdx[dir];

int ny = y + hdy[dir];

if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;

if(board[nx][ny]) continue;

if(dist[a+1][nx][ny]) continue; // 이미 해당 차원에서 전에 더 빠른 루트가 있었음

dist[a+1][nx][ny] = dist[a][x][y] + 1; // 말처럼 이동한 횟수(차원)를 늘려주고 거리를 계산해서 써줌

q.push({a+1,nx,ny});

}

}

for(int dir=0; dir<4; dir++){

int nx = x + dx[dir];

int ny = y + dy[dir];

if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;

if(board[nx][ny]) continue;

if(dist[a][nx][ny]) continue; // 이미 해당 차원에서 전에 더 빠른 루트가 있었음

dist[a][nx][ny] = dist[a][x][y] + 1;  

q.push({a,nx,ny}); // 기본적으로 이동할때는 차원을 늘려주지 않는다. 

}

}

 

일단 말처럼 움직일때는 말처럼 움직인 횟수가 K 이하 일때만 큐에 넣을수 있게 해준다. 이렇게하면 횟수가 K이상일때 더이상 큐에 들어가지 않는다.

근데 말처럼 움직이지 않을수 있는 경우도 큐에 넣어줘야 모든 경우의수가 고려된다. 이 부분때문에 답지를 봤는데 답은 간단했다.

그냥 기본적으로 움직일때도 큐에 넣어버리면 말처럼 움직이지 않을때 상황의 경우가 다 고려가 된다. 이게 두번 큐에 넣는것 같아서 코드에서 거부감이 들지만 사실 12가지의 움직임를 모두 고려해야돼서 타당하고 단지 말처럼 움직인 횟수가 K이상일때만을 거르면 되는것이다. 헷갈린다면 큐에서 꺼낼때를 생각해보고 손으로 써가면서 따라가보면 이 방법이 맞다는것을 알수 있을것이다. 즉 큐에서 꺼낼때 a값이 0부터 K까지 모든 값이 될수 있기 때문에 모든경우가 고려된다는 것이다. 

 

전체 코드는 아래와 같다.

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

int board[205][205];

// K가 최대 30
int dist[32][205][205];

int k;
int w,h;

// 말처럼 무빙
int hdx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int hdy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; 


// 원숭이 기본 무빙 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> k;
  cin >> w >> h;

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

  queue<tuple<int,int,int>> q;
  q.push({0,0,0});

  //원래 처음시작일때는 0 이지만 편의상 1로 생각하고 마지막에 빼준다.
  dist[0][0][0] = 1;

  int ans = 2000000000;

  while (!q.empty())
  {
    int a,x,y;
    tie(a,x,y) = q.front(); q.pop();

    if(a < k){
      for(int dir=0; dir<8; dir++){
        int nx = x + hdx[dir];
        int ny = y + hdy[dir];

        if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
        if(board[nx][ny]) continue;
        if(dist[a+1][nx][ny]) continue; // 이미 해당 차원에서 더 빠른 루트가 있었음

        dist[a+1][nx][ny] = dist[a][x][y] + 1; // 말처럼 이동한 횟수를 늘려주고 거리를 계산해서 써줌
        q.push({a+1,nx,ny}); // 말처럼 움직인 횟수를 1 증가시키고 큐에 넣는다.
      }
    }

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

      if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
      if(board[nx][ny]) continue; // 이미 해당 차원에서 더 빠른 루트가 있었음
      if(dist[a][nx][ny]) continue;  // 기본적으로 이동할때는 횟수을 늘려주지 않는다. 
      dist[a][nx][ny] = dist[a][x][y] + 1;
      q.push({a,nx,ny}); // 기본적으로 이동할때는 횟수을 그대로 큐에 넣는다.
    }


  }

  // 주의 0~k번 까지임
  for(int i=0; i<k+1; i++){
    if(dist[i][h-1][w-1]) ans = min(ans, dist[i][h-1][w-1]);
  }

  if(ans == 2000000000) cout << -1 << '\n';
  else cout << ans - 1 << '\n';
  


}