BOJ 19236, 청소년 상어

Source: BOJ 19236 청소년 상어

청소년 상어

처음에는 기본적인 bfs, 백트래킹 문제인 줄 알았으나 FISH라는 구조체와 board판의 동기화가 핵심이었던 문제
또 백트래킹을 하기 위해서 상태를 나타내는 보드판의 이전값을 저장하는 것이 핵심이었다
solve함수에 상태를 저장한 보드판, 물고기의 정보, 잡아먹을 물고기의 좌표, 현재까지의 잡아먹은 물고기의 합을
넘겨주어 solve함수 내에서 각각의 보드판과 물고기의 정보의 복제본을 만들어 계산해주었다.

PS Logic

1. 현재 상태를 저장할 board[4][4], 물고기의 정보를 저장할 구조체 FISH를 만든다
2. 입력으로 주어지는 물고기의 정보와 보드판을 넣어 초기화해준다
3. solve함수에 보드판, 물고기의 정보를 넘겨주고 내부에서 복제본을 만들어 물고기 먹기, 물고기 이동, 상어의 이동을 처리한다

#include <bits/stdc++.h>
using namespace std;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
struct FISH
{
  int x, y;
  int dir;
};
int board[4][4];
FISH fish[16];
int ans;

void solve(int board[4][4], FISH fish[16], int shark_x, int shark_y, int sum){
  int copy_board[4][4];
  FISH copy_fish[16];
  for(int i=0; i<4; i++){
    for(int j=0; j<4; j++){
      copy_board[i][j] = board[i][j];
    }
  }
  for(int i=0; i<16; i++){
    copy_fish[i] = fish[i];
  }
  //eat
  int fish_num = copy_board[shark_x][shark_y];
  int shark_dir = copy_fish[fish_num].dir;
  copy_fish[fish_num].x = -1;
  copy_fish[fish_num].y = -1;
  copy_fish[fish_num].dir = -1;
  copy_board[shark_x][shark_y] = -1;
  sum += (fish_num + 1);
  if(ans < sum) ans = sum;

  //copy_fish move
  for(int f=0; f<16; f++){
    if(copy_fish[f].x == -1) continue;
    int cx = copy_fish[f].x;
    int cy = copy_fish[f].y;
    int cd = copy_fish[f].dir;
    int nx = cx + dx[cd];
    int ny = cy + dy[cd];
    int nd = cd;
    while(nx<0||ny<0||nx>=4||ny>=4 || (nx==shark_x && ny==shark_y)){
      nd = (nd + 1) % 8;
      nx = cx + dx[nd];
      ny = cy + dy[nd];
    }

    if(copy_board[nx][ny] != -1){
      int target = copy_board[nx][ny];
      copy_fish[target].x = cx;
      copy_fish[target].y = cy;
      copy_fish[f].x = nx;
      copy_fish[f].y = ny;
      copy_fish[f].dir = nd;
      copy_board[nx][ny] = f;
      copy_board[cx][cy] = target;
    }
    else{
      copy_board[nx][ny] = f;
      copy_fish[f].x = nx;
      copy_fish[f].y = ny;
      copy_fish[f].dir = nd;
      copy_board[cx][cy] = -1;
    }
  }
    //shark move
    for(int step =1; step<4; step++){
      int x = shark_x + dx[shark_dir] * step;
      int y = shark_y + dy[shark_dir] * step;
      if(x<0||x>=4||y<0||y>=4) break;
      if(copy_board[x][y] == -1) continue;
      solve(copy_board, copy_fish, x, y, sum);
    }
  


}
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for(int i=0; i<4; i++){
    for(int j=0; j<4; j++){
      int a, b;
      cin>>a>>b;
      a--;
      b--;
      board[i][j] = a;
      fish[a].x = i;
      fish[a].y = j;
      fish[a].dir = b;
    }
  }
  solve(board, fish, 0, 0, 0);
  cout<<ans;
}