청소년 상어 19236

문제

생략

접근 방법

적혀있는 대로 구현해 주면 된다.
상어의 물고기 먹기-> 살아있는 물고기의 이동->상어의 이동->반복
이렇게 하면 되는데 상어의 이동은 4칸을 확인해서 가능한 곳으로 가면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
struct fish
{
    int dir, y, x;
    bool isDie;
};
struct shark
{
    int dir, y, x, sum;
};
int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dx[] = {0, -1, -1, -1, 0, 1, 1, 1}, ret;
void input(vector<fish> &fishs, vector<vector<int>> &map)
{
    int a, b;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
        {
            cin >> a >> b;
            fishs[a] = {b - 1, i, j, false};
            map[i][j] = a;
        }
}
int nextDir(shark &s, fish cur)
{
    while (true)
    {
        int ny = cur.y + dy[cur.dir];
        int nx = cur.x + dx[cur.dir];
        if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4 || (s.y == ny && s.x == nx))
            cur.dir = (cur.dir + 1) % 8;
        else
            return cur.dir;
    }
}
void eat(shark &s, vector<fish> &fishs, vector<vector<int>> &map)
{
    int fishIdx = map[s.y][s.x];
    s.sum += fishIdx;
    s.dir = fishs[fishIdx].dir;
    fishs[fishIdx].isDie = true;
    map[s.y][s.x] = 0;
}
void dfs(shark s, vector<fish> fishs, vector<vector<int>> map)
{
    eat(s, fishs, map);
    ret = max(s.sum, ret);
    for (int i = 1; i <= 16; ++i)
    {
        fish cur = fishs[i];
        if (cur.isDie)
            continue;
        int cy = cur.y;
        int cx = cur.x;
        int nd = nextDir(s, cur);
        int ny = cy + dy[nd];
        int nx = cx + dx[nd];
        int otherIdx = map[ny][nx];
        fishs[otherIdx].y = cy;
        fishs[otherIdx].x = cx;
        fishs[i].y = ny;
        fishs[i].x = nx;
        fishs[i].dir = nd;
        map[cy][cx] = otherIdx;
        map[ny][nx] = i;
    }
    for (int i = 1; i < 4; ++i)
    {
        int ny = s.y + dy[s.dir] * i;
        int nx = s.x + dx[s.dir] * i;
        if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4)
            break;
        else if (map[ny][nx] == 0)
            continue;
        shark n = s;
        n.y = ny;
        n.x = nx;
        dfs(n, fishs, map);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    vector<fish> fishs(17);
    vector<vector<int>> map(4, vector<int>(4));
    input(fishs, map);
    shark s = {0, 0, 0, 0};
    dfs(s, fishs, map);
    cout << ret;
    return 0;
}

풀이

아무리 구석이라도 8면이 막힐 일은 없으니 물고기 방향은 while문으로 구해도 된다.
효율적으로 작성해 보려고 변수를 줄이려 했는데 그러다가 꼬여서 시간만 더 버렸다.
다른 사람의 풀이를 보니 상어를 따로 관리해 주는 게 덜 헷갈려서 참고했다.