[ BOJ - 19237번 ] 어른 상어 (C++)

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

 다른 삼성 기출 문제들과 비슷한 구현, 시뮬레이션 문제라고 생각해, 시간 초과에는 크게 신경쓰지 않고 접근 방법과 구현 계획을 시간을 들여 확실하게 생각한 뒤 실수하지 않고 정확하게 구현하는데 집중하여 문제를 해결하였다.

 

[ 풀이 방법 ]

 

1. 번호, 위치, 이동 방향, 방향에 따른 이동 방향 우선순위, 제거되었는지 여부를 멤버 변수로 갖는 상어 구조체를 담는 배열,

2. 상어의 위치를 표시하는 2차원 배열,

3. 냄새를 담을 2차원 배열,

4. 냄새가 없어지기 까지 남은 시간을 저장할 2차원 배열이 필요

struct Shark {
    int num;
    int x; int y;
    int dir;
    vector<vector<int>> priority;
    bool removed;
};

vector<vector<int>> board;
vector<vector<int>> smell;
vector<vector<int>> timeLeft;
vector<Shark> sharks;

 

1. 상어 이동 기능

  1. 상어 구조체 배열을 이용해 순회하며 상어를 이동

 

  2. 상어 이동 시, 상어 구조체와 board의 정보를 모두 갱신해야 한다.

   - 상어가 이동한 후의 위치만을 처리하기 위해 board를 복사한 aux 배열을 사용하여 이동을 처리한 후, board와 aux를 swap하여 구현

 

  3. 상어가 바라보는 방향을 기준으로 주어진 방향 우선순위 순서대로 인접한 칸을 탐색하여, 인접한 칸에 냄새가 남아있지 않을 경우 이동

 

  4. 냄새가 남지 않은 칸이 없는 경우에는 상어가 바라보는 방향을 기준으로 주어진 방향 우선순위 순서대로 인접한 칸을 탐색하여,

  인접한 칸에 자기 냄새가 남은 경우 이동

 

2. 한 칸에 상어가 여러마리 있을 경우 가장 작은 상어를 제외한 다른 상어들 제거 기능

  - 상어가 이동할 위치에 다른 상어가 있을 경우(aux 배열을 이용하여 이동 후의 위치가 중복되는 경우만을 탐색), 

  번호를 비교하여 더 큰 번호의 상어가 제거되도록 구현

 

  - 제거된 상어는 aux에서 이동 전의 위치를 빈칸으로 갱신하고, 상어 구조체에 상어가 제거되었음을 표시하여 다음 이동 시에 제거된 상어는 생략되도록 구현

 

3. 위 과정을 반복하여 1의 번호를 가진 상어만 남았을 때, 반복한 횟수를 출력하는 기능

  - 반복마다 상어 이동 후에 냄새 갱신이 실행되어야 한다.

  즉, 1. 상어 이동과 중복 제거

       2. 냄새의 남은 시간 갱신 및 시간이 지난 냄새 제거

       3. 이동 후 상어가 위치한 칸에 냄새를 추가하고 남은 시간을 K로 저장

  위 순서대로 실행되어야 한다.

 

  - 반복 횟수가 1000번을 넘긴 경우, 반복 종료 후 -1을 출력

 

[ 회고 ]

 유사한 문제를 많이 풀어봤기 때문에 풀이 방법을 생각하고 구현 방법을 계획하는 데 어려움이 없었고, 구현 시에 실수하지 않는 것에 초점을 두고 문제를 풀었다.

 

 입출력 부분을 구현하는 부분에서 실수가 있었으나 핵심 기능은 계획대로 올바르게 구현하였고, 빠르게 디버깅하여 문제를 해결할 수 있었다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Shark {
    int num;
    int x; int y;
    int dir;
    vector<vector<int>> priority;
    bool removed;
};

int N, M, K;

int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

vector<vector<int>> board;
vector<vector<int>> smell;
vector<vector<int>> timeLeft;
vector<Shark> sharks;

int res;

void move() {
    
    vector<vector<int>> aux(board.begin(), board.end());
    for (int idx = 1; idx < int(sharks.size()); idx++) {
        
        if(sharks[idx].removed) continue;
        
        int x = sharks[idx].x;
        int y = sharks[idx].y;
        int dir = sharks[idx].dir;
        
        int nx = 0;
        int ny = 0;
        int nDir = 0;
        
        bool moved = false;
        
        // 냄새가 없는 인접한 칸을 상어가 바라보는 방향의 우선순위 순서로 탐색
        for(int i = 0; i < 4; i++) {
            nDir = sharks[idx].priority[dir][i];
            nx = x + dirX[nDir];
            ny = y + dirY[nDir];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            
            if(!smell[nx][ny]) {
                moved = true;
                break;
            }
        }
        
        if(moved) {
            if(aux[nx][ny]) {
                if(aux[nx][ny] > idx) {
                    sharks[aux[nx][ny]].removed = true;
                } else {
                    sharks[idx].removed = true;
                    aux[x][y] = 0;
                    continue;
                }
            }
        } else {
            
            // 자기 냄새가 있는 인접한 칸을 상어가 바라보는 방향의 우선순위 순서로 탐색
            for(int i = 0; i < 4; i++) {
                nDir = sharks[idx].priority[dir][i];
                nx = x + dirX[nDir];
                ny = y + dirY[nDir];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                
                if(smell[nx][ny] == idx) {
                    moved = true;
                    break;
                }
            }
            
            if(aux[nx][ny]) {
                if(aux[nx][ny] > idx) {
                    sharks[aux[nx][ny]].removed = true;
                } else {
                    sharks[idx].removed = true;
                    aux[x][y] = 0;
                    continue;
                }
            }
        }
        
        aux[nx][ny] = idx;
        aux[x][y] = 0;
        sharks[idx].x = nx;
        sharks[idx].y = ny;
        sharks[idx].dir = nDir;
    }
    
    aux.swap(board);
    vector<vector<int>>().swap(aux);
}

void updateSmell() {
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(smell[i][j]) {
                timeLeft[i][j]--;
                if(!timeLeft[i][j]) smell[i][j] = 0;
            }
        }
    }
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(board[i][j]) {
                smell[i][j] = board[i][j];
                timeLeft[i][j] = K;
            }
        }
    }
}

int countShark() {
    
    int cnt = 0;
    
    for(int i = 1; i < int(sharks.size()); i++) {
        if(!sharks[i].removed) cnt++;
    }
    
    return cnt;
}

void solve() {
    
    while (countShark() > 1) {
        
        res++;
        
        move();
        updateSmell();
        
        if(res > 1000) {
            res = -1;
            return;
        }
    }
    
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> K;
    board.resize(N, vector<int> (N));
    smell.resize(N, vector<int> (N));
    timeLeft.resize(N, vector<int> (N));
    sharks.resize(M+1);
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if(board[i][j]) {
                smell[i][j] = board[i][j];
                timeLeft[i][j] = K;
                
                Shark shark = {board[i][j], i, j, 0, vector<vector<int>>(4, vector<int>(4)), false};
                sharks[board[i][j]] = shark;
            }
        }
    }
    
    for(int i = 1; i <= M; i++) {
        cin >> sharks[i].dir;
        sharks[i].dir--;
    }
    
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j < 4; j++) {
            for(int k = 0; k < 4; k++) {
                int dir;
                cin >> dir;
                dir--;
                
                sharks[i].priority[j][k] = dir;
            }
        }
    }
    
    solve();
    
    cout << res << '\n';
    
    return 0;
}