[19236] 청소년 상어

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

19236번: 청소년 상어

8방향 테이터를 이용한 사칙연산 수준의 구현이지만, 여러가지 조건이 많고, 특히 어떤 자료구조를 잡을지가 문제다.

자료구조의 개수가 많을수록 업데이트를 빼먹는 등의 실수를 할 가능성이 높지만,

퍼포먼스 측면에서 어떨땐 더 유리할 수 있다.

단순히 {번호, 방향, 행, 열}을 vector로만 넣으면 한번 id를 기준으로 sort한 뒤에, 업데이트는 erase()만으로 가능하다.

다만, 물고기의 이동을 구현할때 특정 위치에 물고기가 존재하는가를 판단해야 하는데, 이 부분을 선형탐색해야만 한다.

그래서 위 선형 자료구조와 함께, 선형 자료구조의 인덱스를 저장하는 2차원 배열을 하나 더 두었다.

구현에 꽤나 시간을 쓴 문제인데, 자료구조를 그냥 하나로 줄였으면 조금 더 빠르게 풀었지 않나 싶다.

---

#include <bits/stdc++.h>

using namespace std;

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

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

typedef struct {

    int id, dir, y, x;

} state;

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

int f(int idMap[4][4], state fish[17], int sharkY, int sharkX, int sharkDir) {

    int i, j, id[4][4];

    state a[17];

    for (i = 0; i < 4; i++)

        for (j = 0; j < 4; j++) id[i][j] = idMap[i][j];

    for (i = 1; i <= 16; i++) a[i] = fish[i];

    int curScore = id[sharkY][sharkX];

    sharkDir = a[id[sharkY][sharkX]].dir;

    a[id[sharkY][sharkX]] = {-1, -1, -1, -1};

    id[sharkY][sharkX] = 0;

    for (i = 1; i <= 16; i++) {

        if (a[i].id == -1) continue;

        bool canMove = false;

        int cy = a[i].y, cx = a[i].x;

        int ny, nx, d = a[i].dir;

        for (j = 0; j < 8; j++) {

            ny = cy + dy[d];

            nx = cx + dx[d];

            if (isValid(ny, nx) && (ny == sharkY && nx == sharkX) == false) {

                canMove = true;

                break;

            }

            d = (d == 8) ? 1 : d + 1;

        }

        if (!canMove) continue;

        a[i].dir = d;

        if (1 <= id[ny][nx] && id[ny][nx] <= 16) {

            int nxtId = id[ny][nx], curId = id[a[i].y][a[i].x];

            int nxtY = a[nxtId].y, nxtX = a[nxtId].x;

            int curY = a[curId].y, curX = a[curId].x;

            assert(nxtY != -1 && nxtY != -1 && curY != -1 && curX != -1);

            a[nxtId].y = curY;

            a[nxtId].x = curX;

            a[curId].y = nxtY;

            a[curId].x = nxtX;

            id[curY][curX] = nxtId;

            id[nxtY][nxtX] = curId;

        } else {

            int curId = id[a[i].y][a[i].x];

            int curY = a[curId].y, curX = a[curId].x;

            id[curY][curX] = 0;

            id[ny][nx] = curId;

            a[curId].y = ny;

            a[curId].x = nx;

        }

    }

    int nxtScore = 0;

    for (i = 1;; i++) {

        int y = sharkY + i * dy[sharkDir];

        int x = sharkX + i * dx[sharkDir];

        if (isValid(y, x) == false) break;

        if (1 <= id[y][x] && id[y][x] <= 16) {

            nxtScore = max(f(id, a, y, x, sharkDir), nxtScore);

        }

    }

    return curScore + nxtScore;

}

int main(void) {

    ios_base::sync_with_stdio(0), cin.tie(0);

    int id[4][4];

    state a[17];

    for (int i = 0; i < 4; i++) {

        for (int j = 0; j < 4; j++) {

            int A, B;

            cin >> A >> B;

            id[i][j] = A;

            a[A] = {A, B, i, j};

        }

    }

    cout << f(id, a, 0, 0, 0);

    return 0;

}

---