[백준 19237]어른 상어

A. 접근법

이 문제는 문제의 조건에 따라 잘 구현해야하는 '시뮬레이션' 문제이다.

문제를 구현하기 위해 선언한 자료구조는 다음과 같습니다.

vector<vector<vector<int>>> table

1. table: 문제에서 제시한 표를 표현하는 벡터.
   ex) table[0][4][0] = 3(상어의 자연수 번호), table[0][4][1] = 4(냄새의 존재 시간)

vector<vector<vector<int>>> dp

2. dp(Direction priority): 상어들의 방향에 대한 우선순위를 저장하는 벡터.

vector<int> sd

3. sd(Sharks' direction): 상어들의 현재 방향을 나타내는 벡터.

B. 구현

문제가 틀린 이유는 처음에 아래와 같이 구현을 했기 때문입니다.

if(stg > 1000)
	return -1;
    
    ...
    
if(상어가 한마리이면)
	return stg + 1;
else
	return solver(stg + 1, tc);

그러면 stg는 1000이 가능하고 만약 1001초 후 한마리가 되는 테스트케이스가 주어졌을 때 -1이 아닌 1001을 반환할 수 있기 때문에 틀렸습니다. 실제 시험에서 이런 케이스를 꼭 잘 따져서 처리해야 할 것 같습니다.

C. 코드

#include <iostream>
#include <vector>

using namespace std;

int T, N, M, K;
vector<vector<vector<int>>> table;
vector<vector<vector<int>>> dp;
int dx[4] = { -1, 1, 0, 0};
int dy[4] = { 0, 0, -1, 1};

vector<int> sd;
int valid(int x, int y) {
    if(x < 0 || x >= N || y < 0 || y >= N)
        return 0;
    else
        return 1;
}

int solver(int stg, vector<vector<vector<int>>>& t) {
    if(stg >= 1000)
        return -1;

    vector<vector<vector<int>>> tc(t);

    int i, j, k;

    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            if(tc[i][j][1] != t[i][j][1])
                continue;

            // 상어가 존재한다면
            if(t[i][j][1] == K) {
                // 빈칸을 탐색
                int sn = t[i][j][0] - 1;
                for(k = 0; k < 4; k++) {
                    int dX = dx[dp[sn][sd[sn]][k]];
                    int dY = dy[dp[sn][sd[sn]][k]];
                    int nX = i + dX;
                    int nY = j + dY;
                    // 빈칸을 찾았다!
                    if(valid(nX, nY) && t[nX][nY][0] == 0) {
                        // 빈칸이면 그냥 움직이고
                        if(tc[nX][nY][0] == 0) {
                            tc[nX][nY][0] = sn + 1;
                            tc[nX][nY][1] = K;
                        }
                        // 해당 칸에 누군가 와 있다면 우선순위에 맞추어 상어를 위치시킨다.
                        else {
                            if(tc[nX][nY][0] > sn + 1) {
                                tc[nX][nY][0] = sn + 1;
                                tc[nX][nY][1] = K;
                            }
                        }
                        sd[sn] = dp[sn][sd[sn]][k];
                        break;
                    }
                }

                // 빈 칸을 못 찾아 내 냄새의 칸을 찾는다.
                if(k == 4) {
                    for(k = 0; k < 4; k++) {
                        int dX = dx[dp[sn][sd[sn]][k]];
                        int dY = dy[dp[sn][sd[sn]][k]];
                        int nX = i + dX;
                        int nY = j + dY;
                        // 내 냄새의 칸을 찾았다.
                        if(valid(nX, nY) && t[nX][nY][0] == sn + 1) {
                            tc[nX][nY][0] = sn + 1;
                            tc[nX][nY][1] = K;
                            sd[sn] = dp[sn][sd[sn]][k];
                            break;
                        }
                    }

                }
                tc[i][j][1]--;
            }
            else if(t[i][j][1] < K && t[i][j][1] > 0) {
                tc[i][j][1]--;
            }
            else {
            }
        }
    }

    int cnt = 0;

    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {

            // 상어의 수를 헤아린다.
            if(tc[i][j][1] == K)
                cnt++;
            // 냄새가 사라지면 빈칸으로 만들어준다.
            else if(tc[i][j][1] == 0)
                tc[i][j][0] = 0;
            else {}
        }
    }

    // 상어가 한 마리면 상황 종료.
    if(cnt == 1)
        return stg + 1;
    else
        return solver(stg + 1, tc);

}
int main() {
    T = 1;
    //scanf("%d", &T);
    for(int tc = 0; tc < T; tc++) {
        scanf("%d %d %d", &N, &M, &K);

        table.clear();
        sd.clear();
        dp.clear();
        table.resize(N);
        sd.resize(M);

        int tmp;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                scanf("%d", &tmp);
                vector<int> tv(2, 0);
                if(tmp == 0) {
                    table[i].push_back(tv);
                }
                else {
                    tv[0] = tmp;
                    tv[1] = K;
                    table[i].push_back(tv);
                }
            }
        }
        for(int i = 0; i < M; i++) {
            scanf("%d", &tmp);
            sd[i] = tmp - 1;
        }
        dp.resize(M);
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < 4; j++) {
                vector<int> tv1(4, 0);
                scanf("%d %d %d %d", &tv1[0], &tv1[1], &tv1[2], &tv1[3]);
                tv1[0]--;
                tv1[1]--;
                tv1[2]--;
                tv1[3]--;
                dp[i].push_back(tv1);
            }
        }
        printf("%d\n", solver(0, table));
    }
    return 0;
}

D. 결과