shark2

shark2.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct{
  int x, y, dir;
  bool dead;
} FISH;
int arr[4][4]; // 물고기: 1~16, 상어: -1, 빈칸: 0
FISH fishArr[17]; // 인덱스별(1~16) 물고기 정보
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int ans = 0;

bool available(int x, int y){ return x >= 0 && y >= 0 && x < 4 && y < 4; }

void move_fish(){
  for (int i = 1; i <= 16; i++) {
    if(fishArr[i].dead) continue; // 죽은 물고기는 이동 제외

    // 현재 위치에서 45도씩 돌려보면서 해당 위치에 물고기 살아있으면, 이동
    for (int j = 0; j < 8; j++) {
      int ndir = (fishArr[i].dir + j) % 8;
      int mx = fishArr[i].x;
      int my = fishArr[i].y;
      int nx = mx + dx[ndir];
      int ny = my + dy[ndir];
      // 물고기 바라보는 방향이 범위 벗어나지 않으면서, 다른 물고기 있는 위치일 때(상어/빈칸 X)
      if(available(nx, ny)){
        if(arr[nx][ny] > 0){
          fishArr[arr[nx][ny]].x = mx;
          fishArr[arr[nx][ny]].y = my;
          fishArr[i].x = nx;
          fishArr[i].y = ny;
          fishArr[i].dir = ndir;
          swap(arr[mx][my], arr[nx][ny]);
          break;
        } else if(arr[nx][ny] == 0){
          fishArr[i].x = nx;
          fishArr[i].y = ny;
          fishArr[i].dir = ndir;
          swap(arr[mx][my], arr[nx][ny]);
          break;
        }
      }
    }
  }
}

void dfs(int nx, int ny, int ndir, int sum){
  ans = max(sum, ans); // 물고기 번호 최대합 업데이트

  // 먼저 현재의 배열 / 물고기 정보 상태를 임시 배열에 불러온다.(백트랙킹용)
  int tmpArr[4][4];
  FISH tmpFarr[17];
  for (int i = 0; i < 4; i++) copy(arr[i], arr[i]+4, tmpArr[i]);
  copy(fishArr, fishArr+17, tmpFarr);

  // 2. 각 물고기들 이동 시작
  move_fish();

  // 3. 물고기 이동 후, 상어이동: 1~3칸 이동 가능한 칸 DFS
  for (int i = 1; i <= 3; i++) {
    int sx = nx + (dx[ndir] * i);
    int sy = ny + (dy[ndir] * i);
    if(!available(sx, sy)) break;
    if(arr[sx][sy] > 0) { // 이동가능하며 해당 칸에 물고기 있을 때,
      int nxt = arr[sx][sy];
      arr[sx][sy] = -1;
      arr[nx][ny] = 0;
      fishArr[nxt].dead = true;
      dfs(sx, sy, fishArr[nxt].dir, sum+nxt);
      fishArr[nxt].dead = false;
      arr[nx][ny] = -1;
      arr[sx][sy] = nxt;
    }
  }

  for (int i = 0; i < 4; i++) copy(tmpArr[i], tmpArr[i]+4, arr[i]);
  copy(tmpFarr, tmpFarr+17, fishArr);
}

int main(){
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      FISH tmpFish = FISH{i,j,0,false};
      cin >> arr[i][j] >> tmpFish.dir;
      tmpFish.dir--;
      fishArr[arr[i][j]] = tmpFish;
    }
  }

  // 1. 상어가 (0,0) 이동 해당 물고기 먹고 dfs 함수 시작
  int nxt = arr[0][0];
  fishArr[nxt].dead = true;
  arr[0][0] = -1;
  dfs(0, 0, fishArr[nxt].dir, nxt);

  cout << ans << endl;

  return 0;
}