[BOJ] 19236 청소년 상어

문제 링크

www.acmicpc.net/problem/19236

풀이

문제에서 요구하는 내용을 그대로 구현하면 되는 구현 문제.
백트랙킹을 이용해 모든 경우의 수를 따져가며 최댓값을 구하면 된다.

이 경우 시간복잡도는 괜찮을까?
처음에 (0, 0) 위치의 물고기를 잡아먹고 시작하므로 남은 물고기는 15마리이며 상어가 움직이는 경우의 수는 많아봤자 3번이다. 따라서 적당히 최악의 연산량을 계산해도 $3^{15}$이며(실제로는 이보다 더 작다), 약 1400만 가량이므로 충분하다.

C++ 코드

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) int(size(x))
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.tie(nullptr)->sync_with_stdio(false)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int MOD = 1e9 + 7;
constexpr int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
constexpr int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 };

int ans = 0;

struct Fish {
    int num;
    int dir;

    Fish() : Fish(0, 0) {}
    Fish(int num, int dir) : num(num), dir(dir) {}
};

int main() {
    fastio;
    Fish fish[4][4];
    pii pos[16];
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            int a, b;
            cin >> a >> b;
            pos[a - 1] = { i, j };
            fish[i][j] = Fish(a, b - 1);
        }
    }

    auto play = [&](auto& s, int sx, int sy, int dir, int sum) -> void {
        // fish
        Fish tFish[4][4]; memcpy(tFish, fish, sizeof fish);
        pii tPos[16]; memcpy(tPos, pos, sizeof pos);

        for (int i = 0; i < 16; ++i) if (pos[i].X != -1) {
            int x = pos[i].X;
            int y = pos[i].Y;
            for (int j = 0; j < 8; ++j) {
                int ndir = (fish[x][y].dir + j) % 8;
                int nx = x + dx[ndir];
                int ny = y + dy[ndir];
                if (nx == sx && ny == sy) continue;
                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

                fish[x][y].dir = ndir;
                if (fish[nx][ny].num != -1) {
                    swap(pos[i], pos[fish[nx][ny].num - 1]);
                    swap(fish[x][y], fish[nx][ny]);
                }
                else {
                    swap(fish[x][y], fish[nx][ny]);
                    pos[i] = { nx, ny };
                }

                break;
            }
        }

        // shark
        bool eat = false;
        while (true) {
            sx += dx[dir];
            sy += dy[dir];
            if (sx < 0 || sx >= 4 || sy < 0 || sy >= 4) break;

            if (fish[sx][sy].num != -1) {
                eat = true;
                int num = fish[sx][sy].num;

                fish[sx][sy].num = -1;
                pos[num - 1].X = -1;
                s(s, sx, sy, fish[sx][sy].dir, sum + num);
                fish[sx][sy].num = num;
                pos[num - 1].X = sx;
            }
        }

        memcpy(fish, tFish, sizeof fish);
        memcpy(pos, tPos, sizeof pos);

        if (!eat) {
            ans = max(ans, sum);
            return;
        }
    };

    pos[fish[0][0].num - 1].X = -1;

    int num = fish[0][0].num;
    fish[0][0].num = -1;

    play(play, 0, 0, fish[0][0].dir, num);

    cout << ans;

    return 0;
}