19237번-어른 상어

문제

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

19237번: 어른 상어

---

접근방법

1) 접근 사고

   1. 상어의 이동

   1-1.  상어의 방향에서 냄새가 없는 경우

   1-2. 냄새가 없다면 상어의 방향에서 냄새가 있는 경우

   

   2.냄새 1씩 감축

   2.현재 상어의 위치에 상어의 냄새 추가

 

의 알고리즘인데 사실 특별한 알고리즘도 없고 그냥 구현하면 되는 문제였다. 그러나 디버깅 단계에서 런타임 오류를 잡아내지 못해서 시간이 정말 오래 걸렸다. 원인은 정말 간단하게도 상어들의 우선순위 방향을 담는 배열인 spd배열에서 크기를 [5][4][4]로 잘못 지정해주었다. 문제에서 상어가 4마리로 이동하는 예제라서 의식의 흐름대로 배열의 크기를 잘 못준 게 원인이었다. 그 외에도 braek문 미추가 등 자잘한 실수가 너무 많았다.

 

2) 시간 복잡도

 

3) 배운 점

디버깅 실력이 향상 되었다.

 

4) PS

디버깅 실력이 중요하다는 걸 느꼈다. 기존의 디버깅 실력이 정말 부족하다는 것도 느꼈고 기존의 디버깅 방식을 바꿔야겠다고도 많이 느꼈다. 문자 출력의 형식으로 디버깅하는 방식이 조금 더 시간적인 측면에서 효율적이라는 걸 깨달았고 디버깅용 함수를 따로 추가해야 하는 것이 좀 더 코드를 보는데 편하다는 것도 느꼈다. 

---

정답 코드

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 21;
int my[] = {-1,1,0,0};
int mx[] = {0,0,-1,1};
 
struct shark{
    int y, x, d, live;
};
struct smell{
    int own, time;
};
struct game{
    int n, m, k;
    smell smells[MAX][MAX];
    int board[MAX][MAX];
    int spd[MAX*MAX][4][4];
    shark sharks[401];
    game(int n, int m, int k) : n(n), m(m), k(k) {}
 
    bool isValid(int y, int x){
        return (y >= 0 && y < n && x >= 0 && x < n);
    }
 
    void init(){
        memset(smells, 0, sizeof(smells));
        memset(board, 0, sizeof(board));
        memset(spd, 0 , sizeof(spd));
        memset(sharks, 0, sizeof(sharks));
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin >> board[i][j];
                if(board[i][j]){
                    sharks[board[i][j]] = {i, j, 0, true};
                    smells[i][j] = {board[i][j], k};
                }
            }
        }
 
        for(int i = 1; i <= m; i++){
            int dir;
            cin >> dir, dir--;
            sharks[i].d = 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--;
                    spd[i][j][k] = dir;
                }
            }
        }
    }
 
    void moveShark(){
        for(int i = 1; i <= m; i++){
            auto[y,x,d,live] = sharks[i];
            bool findFlag = false;
            if(live == true){
                for(int dir = 0; dir < 4; dir++){
                    int ny = y + my[spd[i][d][dir]];
                    int nx = x + mx[spd[i][d][dir]];
                    if(isValid(ny,nx) && smells[ny][nx].own == 0){
                        //이동시키려는 상어의 우선순익 더 높은 경우
                        //상어의 정보 안에 있는(sharks) 좌표값을, 방향을 변경하고,
                        //상어의 보드 값을 갱신시킨다.
                        //이동하는 위치에 있던 상어는 죽인다.
                        if(board[ny][nx] != 0){
                            if(board[ny][nx] > i){
                                sharks[i] = {ny, nx, spd[i][d][dir], true};
                                sharks[board[ny][nx]].live = false;
                                board[ny][nx] = i;
                                board[y][x] = 0;
                            }
                            //이동시키려는 상어의 우선순위가 더 낮아서 죽어야 하는 경우
                            else{
                                board[y][x] = 0;
                                sharks[i].live = false;
                            }
                        }
                        //이동하려는 칸에 아무 상어가 없는 경우라면 위치를 갱신 시켜주고 상어 board값을 갱신한다.
                        else{
                            sharks[i] = {ny, nx, spd[i][d][dir], true};
                            board[y][x] = 0;
                            board[ny][nx] = i;
                        }
                        findFlag = true;
                        break;
                    }
                }
                //상어의 4방향에 냄새만 있는 경우 자신의 냄새가 있는 칸으로 방향을 잡는다.
                if(!findFlag){
                    for(int dir = 0; dir < 4; dir++){
                        int ny = y + my[spd[i][d][dir]];
                        int nx = x + mx[spd[i][d][dir]];
                        if(isValid(ny, nx) && smells[ny][nx].own == i){
                            sharks[i] = {ny, nx, spd[i][d][dir], true};
                            board[ny][nx] = i;
                            board[y][x] = 0;
                            break;
                        }
                    }
                }
            }
        }
    }
 
    //기존 상어들의 냄새를 1씩 감축
    void minusSmell(){
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < n; j++){
                if(smells[i][j].time-- > 0){
                    if(smells[i][j].time == 0){
                        smells[i][j].own = 0;
                    }
                }
            }
        }
    }
 
    //현재 상어의 위치에 냄새를 더해준다.
    void addSmell(){
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] != 0){
                    smells[i][j] = {board[i][j], k};
                }
            }
        }
    }
 
    //상어 1번만 남아있는지 확인 하는 기능
    bool check(){
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] > 1){
                    return false;
                }
            }
        }
        return true;
    }
 
    //디버깅 용도
    void printboard(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cout << board[i][j] <<" ";
            }
            cout <<"\n";
        }
        cout << "====== board =======" <<"\n";
    }
    void printSmell(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cout << smells[i][j].own <<" ";
            }
            cout <<"\n";
        }
        cout << "====== smells =======" <<"\n";
    }
};
 
int main(){
    int n, m, k;
    cin >> n >> m >> k;
    game op(n, m, k);
    op.init();
 
    if(op.check()){
        cout << 0 <<"\n";
        return 0;
    }
 
    for(int t = 1; t <= 1000; t++){
        op.moveShark();
        //op.printboard();
        //op.printSmell();
        op.minusSmell();
        op.addSmell();
        if(op.check()){
            cout <<t <<"\n";
            return 0;
        }
    }
    cout << -1 <<"\n";
    return 0;
}