백준 19236번 문제 풀이

문제 설명

문제를 보고 든 생각

• 구현 문제라서 기능별로 함수를 잘 만들어야겠다.
• 상어와 물고기 정보를 구조체에 담으면 편하겠다.
• 4x4 사이즈이기 때문에 전체탐색해도 부담되지 않을 것 같다.
• 번호가 작은 물고기 먼저 이동시켜야 해서 우선순위 큐를 사용해야 할까?
• 백 트래킹을 구현하기 위해서 저장과 복원을 시도해봐야겠다.

문제 간단 설명

1. 물고기를 우선순위 큐에 넣기 보단 구조체 배열을 만들어서 1번 물고기부터 16번 물고기까지 순서대로 탐색하며 이동시켰다.
2. 상어의 이동 거리를 1, 2, 3으로 나눠서 dfs 탐색을 했다.
3. 물고기 방향을 결정하는 함수 fishDir
   물고기를 swap하는 함수 swapFish
   물고기 전체를 이동시키는 함수 moveFish
   상어를 이동시키는 함수 moveShark
   이렇게 기능별로 함수를 나눴다.
4. dfs에서 기존의 tank와 fish 배열의 정보를 저장하고 재귀 호출을 하고 난 뒤 다시 복원시켜서 반복문을 돌렸다.

코드

#include <iostream>

#define MAX_N 4

using namespace std;

struct strt{
  int num;
  int r, c;
  int dir;
};

int dir[9][2] = {{0, 0}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
strt fish[18];
int tank[MAX_N][MAX_N];

void getInput(){
  fish[0] = {0, -1, -1, -1};
  for(int r=0; r<MAX_N; ++r){
    for(int c=0; c<MAX_N; ++c){
      int num, dir; cin >> num >> dir;
      fish[num] = {num, r, c, dir};
      tank[r][c] = num;
    }
  }
}

int fishDir(strt fish){
  for(int i=0; i<8; ++i){
    int currDir = i + fish.dir;
    if(currDir > 8){
      currDir -= 8;
    }

    int nr = fish.r + dir[currDir][0], nc = fish.c + dir[currDir][1];
    if(nr < 0 || nc < 0 || nr >= MAX_N || nc >= MAX_N){
      // out of bound
      continue;
    }

    if(tank[nr][nc] == 17){
      // shark
      continue;
    }

    return currDir;
  }

  // cannot move
  return -1;
}

void swapFish(strt _fish, int _r, int _c){
  int otherFishNum = tank[_r][_c];
  if(otherFishNum != 0){
    fish[otherFishNum].r = _fish.r;
    fish[otherFishNum].c = _fish.c;
    tank[_r][_c] = _fish.num;

    tank[_fish.r][_fish.c] = otherFishNum;
    fish[_fish.num].r = _r;
    fish[_fish.num].c = _c;
  } else{
    tank[_r][_c] = _fish.num;
    tank[_fish.r][_fish.c] = 0;
    fish[_fish.num].r = _r;
    fish[_fish.num].c = _c;
  }

}

void moveFish(){
  for(int i=1; i<=16; ++i){
    strt currFish = fish[i];
    if(currFish.num == 0){
      // died
      continue;
    }
    
    int _fishDir = fishDir(currFish);
    if(_fishDir == -1){
      // cannot move
      continue;
    }
    currFish.dir = _fishDir;
    fish[i].dir = _fishDir;

    int nr = currFish.r + dir[_fishDir][0], nc = currFish.c + dir[_fishDir][1];
    if(nr < 0 || nc < 0 || nr >= MAX_N || nc >= MAX_N){
      continue;
    }

    swapFish(fish[i], nr, nc);
  }
}

int moveShark(int r, int c, int _dir, int dist){
  int nr = r + dir[_dir][0]*dist, nc = c + dir[_dir][1]*dist;
  if(nr < 0 || nc < 0 || nr >= MAX_N || nc >= MAX_N){
    // out of bound
    return -987654321;
  }
  if(tank[nr][nc] == 0){
    // no fish
    return -987654321;
  }

  // eat
  int eatenFish = tank[nr][nc];
  tank[nr][nc] = 17;
  fish[17].r = nr;
  fish[17].c = nc;
  fish[17].dir = fish[eatenFish].dir;
  fish[eatenFish].num = 0;
  tank[r][c] = 0;

  return eatenFish;
}

// dfs after shark ate (0, 0)
int dfs(int _r, int _c, int val){
  if(_r < 0 || _c < 0 || _r >= MAX_N || _c >= MAX_N){
    // out of bound
    return val;
  }

  moveFish();

  // save
  int _tank[MAX_N][MAX_N];
  for(int r=0; r<MAX_N; ++r){
    for(int c=0; c<MAX_N; ++c){
      _tank[r][c] = tank[r][c];
    }
  }
  strt _fish[18];
  for(int i=1; i<=17; ++i){
    _fish[i] = fish[i];
  }

  int ret = val;

  for(int dist=1; dist<=3; ++dist){
    strt shark = fish[17];
    int nr = shark.r + dir[shark.dir][0]*dist, nc = shark.c + dir[shark.dir][1]*dist;
    if(nr < 0 || nc < 0 || nr >= MAX_N || nc >= MAX_N){
      // out of bound
      continue;
    }
    if(tank[nr][nc] == 0){
      // no fish to eat
      continue;
    }

    // eat fish
    int score = moveShark(shark.r, shark.c, shark.dir, dist);
    // dfs, choose max val from dist 1, 2, 3
    ret = max(ret, dfs(nr, nc, val + score));

    // recovery tank and fish
    for(int r=0; r<MAX_N; ++r){
      for(int c=0; c<MAX_N; ++c){
        tank[r][c] = _tank[r][c];
      }
    }
    for(int i=1; i<=17; ++i){
      fish[i] = _fish[i];
    }
  }

  return ret;
}


int solve(){
  getInput();
  int val = tank[0][0];
  fish[val].num = 0;
  tank[0][0] = 17;

  fish[17].r = 0;
  fish[17].c = 0;
  fish[17].num = 17;
  fish[17].dir = fish[val].dir;

  val = dfs(0, 0, val);

  return val;
}

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

  cout << solve();

  return 0;
}