백준 19236번 : 청소년 상어 - 백트래킹 Cpp

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

#include <bits/stdc++.h>

using namespace std;


int dx[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

int ans = 0;

void moveFish(int _curFishPosition[][4], int _curFishes[][3], int _skx, int _sky) {
    for (int i = 1; i <= 16; i++) {
        int x = _curFishes[i][0];
        int y = _curFishes[i][1];
        int d = _curFishes[i][2];


        if (x < 0) continue;

        int nx = x;
        int ny = y;
        int nd = d;
        for (int j = 0; j < 8; j++) {
            nx = x + dx[nd];
            ny = y + dy[nd];
            nd++;
            if (nd >= 9) nd = 1;

            if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;
            if (nx == _skx && ny == _sky) continue;

            break;
        }

        nd--;
        if (nd == 0) nd = 8;


        _curFishes[i][0] = nx;
        _curFishes[i][1] = ny;
        _curFishes[i][2] = nd;


        if(_curFishPosition[nx][ny]<=0){
            cout << "Erorr!!" << '\n';
            cout <<_curFishPosition[nx][ny] << ' ' << nx << ' ' << ny << '\n';
        }

        int changeFish = _curFishPosition[nx][ny];
        //살은 경우만 x,y 동기화해줌
        if(_curFishes[changeFish][0] >= 0) {
            _curFishes[changeFish][0] = x;
            _curFishes[changeFish][1] = y;
        }

        swap(_curFishPosition[nx][ny], _curFishPosition[x][y]);

    }
}


void backTrack(int L, int _skx, int _sky, int _skd, int _fishPosition[][4], int _fishes[][3], int sum) {
    ans = max(ans, sum);
    int curFishes[17][3];
    int curFishPosition[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            curFishPosition[i][j] = _fishPosition[i][j];
        }
    }
    for (int i = 0; i < 17; i++) {
        for (int j = 0; j < 3; j++) {
            curFishes[i][j] = _fishes[i][j];
        }
    }

    //물고기 이동
    moveFish(curFishPosition, curFishes, _skx, _sky);



    //상어 이동
    int n_skx = _skx;
    int n_sky = _sky;
    int n_skd = _skd;

    for (int i = 0; i < 4; i++) {
        n_skx += dx[_skd];
        n_sky += dy[_skd];


        if (n_skx < 0 || n_skx >= 4 || n_sky < 0 || n_sky >= 4) continue;
        int curFish = curFishPosition[n_skx][n_sky];
        int curFishX = curFishes[curFish][0];

        //물고기 없는 칸 인경우 x==-1
        if (curFishX < 0) continue;
        n_skd = curFishes[curFish][2];

        curFishes[curFish][0] = -1;
        backTrack(L + 1, n_skx, n_sky, n_skd, curFishPosition, curFishes, sum + curFish);
        curFishes[curFish][0] = curFishX;
    }
}


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

    int fishPosition[4][4];

//16fishes x, y, dir;
    int fishes[17][3];


    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            int a, b;
            cin >> a >> b;

            fishPosition[x][y] = a;
            fishes[a][0] = x;
            fishes[a][1] = y;
            fishes[a][2] = b;
        }
    }

    int skx = 0;
    int sky = 0;

    //잡아먹으면 0으로 표시
    ans += fishPosition[skx][sky];
    int skd = fishes[fishPosition[skx][sky]][2];
    fishes[fishPosition[skx][sky]][0] = -1;
    backTrack(0, skx, sky, skd, fishPosition, fishes, ans);

    cout << ans << '\n';
}