[백준 19236]청소년 상어

A. 접근법

-자료구조

1. vector<vector<vector<int>>> table : 4X4 공간의 물고기의 번호와 방향을 저장
2. vector<vector<int>> fish: 0(상어)와 1부터 16까지의 물고기의 좌표와 방향을 저장

위의 2번의 자료구조를 추가한 이유는 물고기가 이동할 때 바로 해당 물고기의 좌표를 찾기 위해서 입니다. 지금 생각해보면 어차피 물고기는 16마리로 한정이 되어있기 때문에 굳이 이 자료구조를 만들지 않아도 시간효율성에서 손해가 크지는 않을 것 같습니다.

B. 구현

이 문제는 '시뮬레이션'으로 문제를 잘 따라 구현을 하면 됩니다. 모든 탐색을 DFS기반으로 상어가 움직이 않을 때 까지 탐색한 후 최댓값을 갱신하면 됩니다.

구현 중 제가 한 실수는 물고기가 이동할 칸이 빈칸일 때, 빈칸과 물고기의 정보를 잘 swap해줄 때 물고기의 방향을 그대로 바꾸었습니다. 원래 물고기가 향하는 방향에 바로 빈칸이 없다면 45도씩 방향을 꺽기 때문에 빈칸을 찾았을 때의 방향으로 업데이트를 해줘야합니다. 이 때 테스트케이스는 모두 맞았지만 제출시 틀렸습니다. 해당 경우는 실제 시험에서 매우 위험할 수 있을 것 같기 때문에 assert등 조건이 안되는 경우를 체크를 해줘야겠다라는 생각을 했습니다.

질문들을 읽으며 다른 사람들이 많이 한 실수는 다음과 같습니다.

상어가 이동하는 중에 물고기가 없는 칸이 있어도 그 칸은 건너뛰고 탐색을 계속해야한다.

C. 코드

#include <iostream>
#include <vector>

using namespace std;

int T;
vector<vector<vector<int>>> table;
vector<vector<int>> fish;

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

int answer = 0;
int valid(int x, int y) {
    if(x < 0 || x >= 4 || y < 0 || y >= 4)
        return 0;
    else
        return 1;
}
void moveFish(int idx, vector<vector<vector<int>>>& t, vector<vector<int>>& f) {

    if(f[idx][0] == -1 && f[idx][1] == -1)
        return;

    int fX = f[idx][0];
    int fY = f[idx][1];
    int fD = f[idx][2];

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

        int nD = fD + i;
        if(nD >= 8)
            nD -= 8;
        int nx = fX + dx[nD];
        int ny = fY + dy[nD];

// 격자 밖으로 나가지 않고, 상어가 아닌 경우
        if(valid(nx, ny) && t[nx][ny][0] != 0) {
            int nidx = t[nx][ny][0];

			// 빈칸이 아닌 경우
            if(nidx != -1) {

                vector<int> ttv(2, 0);

                ttv[0] = idx;
                ttv[1] = nD;

                t[fX][fY][0] = t[nx][ny][0];
                t[fX][fY][1] = t[nx][ny][1];

                f[idx][0] = f[nidx][0];
                f[idx][1] = f[nidx][1];
                f[idx][2] = nD;

                f[nidx][0] = fX;
                f[nidx][1] = fY;
                t[nx][ny] = ttv;
            }
            
            //빈칸일 경우
            else {
                t[nx][ny][0] = t[fX][fY][0];
                t[nx][ny][1] = nD;
                f[idx][0] = nx;
                f[idx][1] = ny;
                f[idx][2] = nD;
                t[fX][fY][0] = t[fX][fY][1] = -1;

            }

            break;
        }
    }
}
void solver(int stg, vector<vector<vector<int>>>& t, vector<vector<int>>& f, int sum) {
	//처음에 상어를 위치
    if(stg == 0) {
        int fN = t[0][0][0];
        int fD = t[0][0][1];
        sum += fN;
        f[0].resize(3);
        f[0][0] = f[0][1] = 0;
        f[0][2] = fD;

        table[0][0][0] = 0;

        f[fN][0] = f[fN][1] = f[fN][2] = f[fN][3] = -1;

    }
    
    // 물고기의 이동
    for(int i = 1; i <= 16; i++) {
        moveFish(i, t, f);
    }
	//상어의 이동
    int cx = f[0][0];
    int cy = f[0][1];

    for(int i = 1; i < 4; i++) {
        int nx = cx + dx[f[0][2]] * i;
        int ny = cy + dy[f[0][2]] * i;
        
        if(valid(nx, ny) && t[nx][ny][0] != -1) {

            vector<vector<vector<int>>> cct(t);
            vector<vector<int>> ccf(f);

            int fM = cct[nx][ny][0];
            int fD = cct[nx][ny][1];

            cct[nx][ny][0] = 0;
            cct[nx][ny][1] = fD;
            cct[cx][cy][0] = -1;
            cct[cx][cy][1] = -1;

            ccf[fM][0] = ccf[fM][1] = ccf[fM][2] = -1;
            ccf[0][0] = nx;
            ccf[0][1] = ny;
            ccf[0][2] = fD;

            solver(stg + 1, cct, ccf, sum + fM);
        }
    }
    if(sum > answer)
        answer = sum;
}

int main() {
    //scanf("%d", &T);
    T = 1;
    int i, j;

    for(int tc = 0; tc < T; tc++) {
        fish.clear();
        table.clear();

        fish.resize(17);
        table.resize(4);

        answer = 0;

        for(i = 0; i < 4; i++) {
            table[i].resize(4);
            for(j = 0; j < 4; j++) {
                table[i][j].resize(2);
                scanf("%d %d", &table[i][j][0], &table[i][j][1]);
                table[i][j][1]--;
                fish[table[i][j][0]].resize(3);
                fish[table[i][j][0]][0] = i;
                fish[table[i][j][0]][1] = j;
                fish[table[i][j][0]][2] = table[i][j][1];

            }
        }

        solver(0, table, fish, 0);
        printf("%d\n", answer);
    }

    return 0;
}

D. 결과