[BOJ][삼성기출] 백준 19237번 - 어른 상어 풀이

| |
백준 온라인 저지 백준 19237번 - 어른 상어 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

1

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.


출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.


풀이

꽤 복잡한 편에 속하는 까다로운 시뮬레이션 문제이다. 로직 자체는 매우 단순하나, 조건과 정보의 양이 많다. 상어 방향의 우선순위가 상어의 현재 방향에 따라 다르기 때문에 3차원 배열을 통해 이를 저장해주어야 한다. 또 상어가 냄새를 뿌리므로 냄새를 저장하는 2차원 배열 을 따로 선언해야하며, 상어가 한 칸에 여러마리 있는 상황이 존재하므로 상어를 원소로 갖는 vector 의 2차원 배열 도 필요하다. 그리고 칸 마다 가장 숫자가 작은 상어만 살아남으므로 이를 어떻게 효율적으로 구현할지도 고민해야 할 포인트다.

우선 먼저 캐치해야 할 포인트는 상어가 동시에 움직이므로, 상어를 격자별로 여러마리 저장할 수 있는 자료구조에 임시적으로 옮겨놓고 격자마다 최소 번호를 갖고 있는 상어를 최종 상태를 저장하는 자료구조에 저장해야 한다는 것이다. 전자는 상어 구조체를 원소로 갖는 vector 를, 후자는 격자별로 상어가 한 마리씩만 들어있으므로 일반적인 상어 배열을 선언하면 됨을 알 수 있다.

격자 별로 가장 작은 번호의 상어를 골라내는 방법은 다음과 같은 방법들을 떠올릴 수 있다.

  • 원소의 삭제가 비교적 빠른 list 자료구조와 정렬 을 이용
  • 우선순위 큐 자료구조를 이용해 상어가 추가될 때마다 비교
  • vector 에서 단순히 모든 원소를 순차적으로 비교해 최소 번호 찾기

이 문제와 같이 상어의 개수가 적은 형태에서는 실행 시간에 있어서 위 세가지 방법에 큰 차이는 없겠지만 아무래도 항상 선형 시간복잡도 O(N) 을 보장하고 구현이 단순한 마지막 3번째 방법이 가장 나은 것을 알 수 있다.

냄새를 기록하는 배열에서는 냄새의 번호와 함께 냄새의 유지 시간도 저장해야하므로 pair 객체를 사용하였다.

이 후 반복문을 통해 남은 상어의 수를 확인하며 경과시간을 계속 올려주면 된다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
using namespace std;

struct Shark{
    int n=0,d=0;
    Shark(){}
    Shark(int n, int d):n(n),d(d){}
};

int N,M,K;
int prior[401][4][4];
pair<int,int> smell[20][20];
Shark field[20][20];
vector<Shark> newField[20][20];
const int dy[]={-1,1,0,0};
const int dx[]={0,0,-1,1};

bool inRange(int y, int x){
    return y>=0 && x>=0 && y<N && x<N;
}

int solve(){
    int ret=0;

    while(++ret<=1000){

        // init newField
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                newField[i][j].clear();

        // move shark
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(field[i][j].n==0) continue;
                Shark s=field[i][j];
                bool isMoved=false;
                for(int k=0;k<4;k++){
                    int dir = prior[s.n][s.d][k]-1;
                    int ny=i+dy[dir];
                    int nx=j+dx[dir];
                    if(!inRange(ny,nx)) continue;
                    if(smell[ny][nx].first==0){
                        newField[ny][nx].push_back(Shark(s.n,dir));
                        isMoved=true;
                        break;
                    }
                }
                if(isMoved) continue;
                for(int k=0;k<4;k++){
                    int dir = prior[s.n][s.d][k]-1;
                    int ny=i+dy[dir];
                    int nx=j+dx[dir];
                    if(!inRange(ny,nx)) continue;
                    if(smell[ny][nx].first==s.n){
                        newField[ny][nx].push_back(Shark(s.n,dir));
                        break;
                    }
                }
            }
        }

        // smells timeout
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                if(smell[i][j].first!=0)
                    if(++smell[i][j].second==K)
                        smell[i][j]=make_pair(0,0);

        // init field
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                field[i][j]=Shark(0,0);

        // remove other sharks & set field and smell
        int sharkNum=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(newField[i][j].empty()) continue;
                Shark minShark(1e9,-1);
                for(Shark s:newField[i][j])
                    if(s.n<minShark.n)
                        minShark = s;
                field[i][j]=minShark;
                smell[i][j]=make_pair(minShark.n,0);
                sharkNum++;
            }
        }

        if(sharkNum==1) break;
    }

    return ret>1000?-1:ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>N>>M>>K;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int n; cin>>n;
            if(n==0) continue;
            field[i][j]=Shark(n,-1);
            smell[i][j]=make_pair(n,0);
        }
    }

    vector<int> initDir(M);
    for(int& i:initDir) cin>>i;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(smell[i][j].first!=0)
                field[i][j].d=initDir[field[i][j].n-1]-1;

    for(int i=1;i<=M;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
            cin>>prior[i][j][k];

    cout<<solve();

    return 0;
}
0%