백준 19236번 : 청소년 상어

sol : -

Learnings

• DFS를 연습해야겠다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_F 17
#define MAX_N 4

struct Fish {
    int id;
    int dir;
    int i;
    int j;
    bool alive;

    Fish() : id(-1), dir(-1), i(-1), j(-1), alive(false) {}
};

struct Shark {
    int i;
    int j;
    int dir;
    int score;

    Shark() : i(0), j(0), dir(0), score(0) {}
};

int maxScore;
// 상, 상좌, 좌, 하좌, 하, 하우, 우, 상우
const int ds[9][2] = {
    {0, 0},
    {-1, 0}, {-1, -1}, {0, -1}, {1, -1},
    {1, 0}, {1, 1}, {0, 1}, {-1, 1}
};

bool InGrid(int i, int j) {
    return 0 <= i && i < 4 && 0 <= j && j < 4;
}

void CopyGrid(int src[MAX_N][MAX_N], int dst[MAX_N][MAX_N]) {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            dst[i][j] = src[i][j];
        }
    }
}

void FishMove(int grid[MAX_N][MAX_N], vector<Fish>& fishes, const Shark& shark) {
    for (int id = 1; id < MAX_F; id++) {
        if (!fishes[id].alive) continue;

        int ci = fishes[id].i;
        int cj = fishes[id].j;
        int cd = fishes[id].dir;

        for (int rot = 0; rot < 8; rot++) {
            int nd = cd + rot;
            if (nd > 8) nd -= 8;

            int ni = ci + ds[nd][0];
            int nj = cj + ds[nd][1];

            if (!InGrid(ni, nj)) continue;
            if (shark.i == ni && shark.j == nj) continue;

            fishes[id].dir = nd;

            if (grid[ni][nj] == 0) {
                grid[ci][cj] = 0;
                grid[ni][nj] = id;
                fishes[id].i = ni;
                fishes[id].j = nj;
            }
            else {
                int otherId = grid[ni][nj];

                grid[ni][nj] = id;
                grid[ci][cj] = otherId;

                fishes[otherId].i = ci;
                fishes[otherId].j = cj;

                fishes[id].i = ni;
                fishes[id].j = nj;
            }

            break;
        }
    }
}

void DFS(int grid[MAX_N][MAX_N], vector<Fish> fishes, Shark shark) {
    maxScore = max(maxScore, shark.score);

    FishMove(grid, fishes, shark);

    bool canMove = false;

    for (int dist = 1; dist <= 3; dist++) {
        int ni = shark.i + ds[shark.dir][0] * dist;
        int nj = shark.j + ds[shark.dir][1] * dist;

        if (!InGrid(ni, nj)) break;
        if (grid[ni][nj] == 0) continue;

        canMove = true;

        int nextGrid[MAX_N][MAX_N];
        CopyGrid(grid, nextGrid);

        vector<Fish> nextFishes = fishes;
        Shark nextShark = shark;

        int eatId = nextGrid[ni][nj];

        nextShark.i = ni;
        nextShark.j = nj;
        nextShark.dir = nextFishes[eatId].dir;
        nextShark.score += eatId;

        nextFishes[eatId].alive = false;
        nextGrid[ni][nj] = 0;

        DFS(nextGrid, nextFishes, nextShark);
    }

    if (!canMove) {
        maxScore = max(maxScore, shark.score);
    }
}

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

    int grid[MAX_N][MAX_N];
    vector<Fish> fishes(MAX_F);

    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            int id, dir;
            cin >> id >> dir;

            grid[i][j] = id;
            fishes[id].id = id;
            fishes[id].dir = dir;
            fishes[id].i = i;
            fishes[id].j = j;
            fishes[id].alive = true;
        }
    }

    Shark shark;
    int firstId = grid[0][0];
    shark.i = 0;
    shark.j = 0;
    shark.dir = fishes[firstId].dir;
    shark.score = firstId;

    fishes[firstId].alive = false;
    grid[0][0] = 0;

    maxScore = shark.score;
    DFS(grid, fishes, shark);

    cout << maxScore;
    return 0;
}