[백준] 19237: 어른 상어(C++)

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

19237번: 어른 상어

 

상어는 왜 풀어도 풀어도 나올까요? 할아버지 상어와 할머니 상어, 엄마 상어 아빠 상어도 있을까요? 핑크퐁 식으로...

 

소요 시간

골드 2 기준 1시간 10분 정도 소요되었습니다. 다른 것보다도 문제를 어떻게 풀지 구상하는 것이 약간 까다로운 문제였다고 생각이 됩니다.

아주 약간의 난이도가 있는 시뮬레이션 문제라고 생각되는데, 이런 문제의 특징이 깔끔하게 구현하지 않아서 뭔가 중간에 꼬이는 부분이 발생하면 디버깅이 골치 아프다는 것입니다. 이 문제도 마찬가지로 구조체를 활용하고, 함수를 분리하여 헷갈리지 않게 깔끔하게 구현하는 것이 중요했다고 생각됩니다.

 

구상

시뮬레이션은 [1) 상어마다 자리에 냄새를 뿌린다. 2) 상어를 이동시킨다 3) 겹치는 자리에 있는 상어를 쫒아낸다. 4) 이전에 있던 냄새를 -1 감소 5) 상어마다 자리에 냄새를 뿌린다. 6) 1번 상어만 남았는지 확인하고, 그렇지 않은 경우 2~6을 반복한다.] 의 과정으로 일어납니다.

필요한 함수는

1) 자리에 냄새를 뿌리는 함수

2) 상어를 이동시키는 함수

3) 겹치는 자리의 상어를 쫒아내는 함수

4) 냄새를 -1 감소하는 함수

5) 1번 상어만 남았는지 확인하는 함수

입니다. 시키는 대로 구현하면 되는데, 이 문제의 어려운 점은 상어의 위치, 방향, 쫒겨났는지 여부, 이동의 우선순위, 각 냄새의 위치, 냄새가 사라지기까지 남은 시간 등의 많은 정보들을 어떻게 관리할 것인가입니다.

저의 경우에는 상어와 관련된 정보들(위치, 방향, 쫒겨났는지 여부, 이동의 우선순위)을 구조체로 만들어 vector에 저장했습니다. 그리고 냄새와 관한 정보는 문제의 그림에 나와 있던 것과 마찬가지로 NxN 배열에 pair로 저장했습니다.

이렇게 한 이유는 냄새의 경우에는 상어의 이동 방향을 결정하는 과정에서 좌표로 접근할 일이 많은 반면, 상어의 경우에는 좌표로 접근할 일이 없기 때문입니다. 겹치는 상어를 확인하는 것에서 좌표로 접근이 필요하다고 생각해서 그렇게 하신 분들도 있을 것 같습니다. NxN 배열에 상어를 저장하는 방식으로요. 저는 '동시에 이동'을 하기 위해서는 상어의 vector를 관리하는게 공간적으로 경제적일 뿐만 아니라 코드의 모양 측면에서 더 깔끔하다고 생각하여 겹치는 상어를 확인하는 M^2의 시간복잡도를 감수했습니다. 이번 턴에 다른 쪽으로 이동할 상어인데 이번 턴에 이미 이동해서 겹치는 자리에 있는 거라고 판단하면 안되니까 결국 동일한 크기의 배열을 복사해서 마지막에 다시 붙여넣어야 하니까요 불편하고 공간 낭비가 심하다고 생각했습니다. 지금 생각해 보니 제 방식으로 구현해도 M 시간복잡도로 선형 탐색하면서 메모를 해두면 굳이 M^2를 감수하진 않아도 될 것 같기도 하네요. 당시에 제가 좀 바빴나 봅니다...

 

코드

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<queue>
#include<cmath>
#include<algorithm>

using namespace std;

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

struct shark {
    int x; int y; int number;
    int dir; bool isdead;
    vector<vector<int> > ranks;
    shark() {
        x = 0; y = 0; number = 0;
        dir = 0; isdead = false; 
        ranks.resize(5); //1~4 사용
        for(int i=0; i<=4; i++) {
            ranks[i].resize(4);
        }
    }
    shark(int nx, int ny, int nn, int nd, bool ni, vector<vector<int> > nr) {
        x = nx; y = ny; number = nn;
        dir = nd; isdead = ni;
        ranks = nr;
    }
};
vector<shark> sharks;
vector<vector<pair<int, int> > > smell;

void make_smell(int k) {
    for(int i=1; i<sharks.size(); i++) {
        if(sharks[i].isdead) continue;
        shark s = sharks[i];
        smell[s.x][s.y] = pair<int, int>(s.number, k);
    }
}

void move_sharks(int n) {
    for(int i=1; i<sharks.size(); i++) {
        if(sharks[i].isdead) continue;
        shark s = sharks[i];
        int dir = s.dir; int x = s.x; int y = s.y;
        int nx = x; int ny = y; int ndir = dir;
        vector<vector<int> > rank = s.ranks;
        for(int j=0; j<4; j++) {
            nx = x + dx[rank[dir][j]]; ny = y + dy[rank[dir][j]];
            if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1 || smell[nx][ny].first != 0) continue;
            else {
                ndir =rank[dir][j]; break;
            }
        }
        if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1 || smell[nx][ny].first != 0) {
            //냄새가 없는 칸이 없다. 자기 냄새가 있는 칸을 선택
            for(int j=0; j<4; j++) {
                nx = x + dx[rank[dir][j]]; ny = y + dy[rank[dir][j]];
                if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1 || smell[nx][ny].first != s.number) continue;
                else {
                    ndir = rank[dir][j]; break; 
                }
            }
        }
        sharks[i].dir = ndir; sharks[i].x = nx; sharks[i].y = ny;
    }
}

void remove_smell(int n) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(smell[i][j].first == 0) continue;
            smell[i][j].second -= 1;
            if(smell[i][j].second == 0) smell[i][j].first = 0;
        }
    }
}

void remove_sharks() {
    for(int i=1; i<sharks.size(); i++) { 
        if(sharks[i].isdead) continue;
        for(int j=i+1; j<sharks.size(); j++) {
            if(sharks[j].isdead) continue;
            if(sharks[i].x == sharks[j].x && sharks[i].y == sharks[j].y) {
                if(sharks[i].number > sharks[j].number) {
                    sharks[i].isdead = true;
                    break;
                }
                else {
                    sharks[j].isdead = true;
                }
            }
        }
    }
}

bool isOver() {
    for(int i=2; i<sharks.size(); i++) {
        if(sharks[i].isdead == false) return false;
    } 
    return true;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;

    smell.resize(n);
    for(int i=0; i<n; i++) {
        smell[i].resize(n);
    }
    for(int i=0; i<=m; i++) {
        sharks.push_back(shark());
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int a; cin >> a;
            if(a != 0) {
                sharks[a].x = i; sharks[a].y = j;
                sharks[a].number = a;
            }
        }
    }
    for(int i=1; i<=m; i++) {
        cin >> sharks[i].dir;
    }
    for(int i=1; i<=m; i++) {
        for(int j=1; j<5; j++) {
            for(int k=0; k<4; k++)
                cin >> sharks[i].ranks[j][k];
        }
    }

    make_smell(k);
    for(int i=1; i<=1000; i++) {
        move_sharks(n);
        remove_smell(n);
        remove_sharks();
        make_smell(k);
        if(isOver()) {
            cout << i << endl; 
            break;
        }
        if(i == 1000) {
            cout << "-1\n"; 
            break;
        }
    }
    return 0;
}