[삼성 기출] 백준 21611번 마법사 상어와 블리자드 풀이

| |
백준 온라인 저지 21611번 - 마법사 상어와 블리자드 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

문제 보러가기


입력

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 격자에 들어있는 구슬의 정보가 주어진다. r번째 행의 c번째 정수는 (r, c)에 들어있는 구슬의 번호를 의미한다. 어떤 칸에 구슬이 없으면 0이 주어진다. 상어가 있는 칸도 항상 0이 주어진다.

다음 M개의 줄에는 블리자드 마법의 방향 di와 거리 si가 한 줄에 하나씩 마법을 시전한 순서대로 주어진다.


출력

첫째 줄에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력한다.


제한

  • 3 ≤ N ≤ 49
  • N은 홀수
  • 1 ≤ M ≤ 100
  • 1 ≤ di ≤ 4
  • 1 ≤ si ≤ (N-1)/2
  • 칸에 들어있는 구슬이 K개라면, 구슬이 들어있는 칸의 번호는 1번부터 K번까지이다.
  • 입력으로 주어진 격자에는 4개 이상 연속하는 구슬이 없다.


풀이

문제의 핵심이자 가장 난관인 부분은 바로 격자를 토네이도 방향으로 탐색해야 한다는 것이다. 처음이라면 당황할 수 있지만 사실 이러한 토네이도 방식의 문제를 삼성에서는 이미 한 번 출제했던 적이 있다. 마법사 상어와 토네이도가 바로 그 것이다. 심지어 본 문제와 토네이도 방향도 일치하므로, 위 문제에서 토네이도 탐색을 제대로 익혀놓았다면 문제를 풀기 훨씬 수월했을 것이다. 사실 토네이도 탐색만 아니라면 조금 귀찮을 수 있는 구현들을 차례대로 나열해놓은 평범한 시뮬레이션 문제이다.

토네이도 방향 탐색을 하기 위해서는 탐색 순서에서 일정한 패턴을 찾아야 한다. 조금만 고민해보면 다음과 같은 패턴을 발견할 수 있다.

좌 1 하 1 -> 우 2 상 2 -> 좌 3 하 3 -> . . . 우 N-1 상 N-1 -> 좌 N-1

좌 하 우 상 이라는 일정한 네 방향에 대해 순차적으로 진행하고, 이동하는 칸 수는 방향을 두 번 변경할 때마다 1씩 증가한다. 마지막에만 예외적으로 좌 N-1 로 마무리한다.

또 한 가지 구현이 갈릴 수 있는 부분은 바로 구슬들을 앞 쪽부터 빈 칸을 채워가며 차곡차곡 정렬하는 과정이다. 필자는 벡터에 0을 제외한 모든 구슬들을 순차적으로 담은 다음, 다시 격자를 순차적으로 돌면서 넣어주고 남은 뒷부분은 모두 0으로 채워주는 식으로 구현했다. 한 마디로 새로운 배열을 만든 뒤 덮어씌워주는 방식으로 하였다. 격자판의 사이즈가 매우 작아 시간 초과를 걱정할 일이 없으므로 이와 같이 직관적인 방식으로 구현함으로써 실수를 줄일 수 있었다.


전체 코드

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <vector>
#define y first
#define x second
using namespace std;

typedef pair<int,int> point;

int N,M;
int board[49][49];
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};
int torDy[] = {0,1,0,-1};
int torDx[] = {-1,0,1,0};

int marble[3];
bool flag=false;

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

void blizzard(point p, int d, int s) {
    while(s--) {
        p.y+=dy[d];
        p.x+=dx[d];
        board[p.y][p.x] = 0;
    }
}

void sort(point p) {
    vector<int> v;

    int dir = 0;
    for(double i=1.0;i<=N;i+=0.5) {
        for(int j=0;j<(int)i;j++) {
            p.y+=torDy[dir%4];
            p.x+=torDx[dir%4];
            if(!inRange(p.y,p.x)) break;
            if(board[p.y][p.x] != 0)
                v.push_back(board[p.y][p.x]); // 0이 아닌 구슬 담기
        }
        dir++;
    }

    // N * N 사이즈 맞춰주기 - 0으로 채움
    v.resize(N*N);
    
    p.y = N/2, p.x = N/2;
    dir = 0;
    int idx = 0;
    for(double i=1.0;i<=N;i+=0.5) {
        for(int j=0;j<(int)i;j++) {
            p.y+=torDy[dir%4];
            p.x+=torDx[dir%4];
            if(!inRange(p.y,p.x)) break;
            board[p.y][p.x] = v[idx++]; // 덮어쓰기
        }
        dir++;
    }
}

// 구슬 폭파 및 기록
void makeZero(vector<point>& v) {
    flag=true;
    for(point p:v) {
        marble[board[p.y][p.x]-1]++;
        board[p.y][p.x] = 0;
    }
}

void boom(point p) {
    int num=0,cnt=0;
    vector<point> log;

    int dir = 0;
    for(double i=1.0;i<=N;i+=0.5) {
        for(int j=0;j<(int)i;j++) {
            p.y+=torDy[dir%4];
            p.x+=torDx[dir%4];
            if(!inRange(p.y,p.x)) break;
            if(num!=board[p.y][p.x]) {
                if(cnt >= 4) makeZero(log);
                log.clear();
                num = board[p.y][p.x];
                cnt = 1;
            }
            else cnt++;
            log.push_back({p.y,p.x});
        }
        dir++;
    }
}

void change(point p) {
    vector<int> v;
    int num=0, cnt=0;

    int dir = 0;
    for(double i=1.0;i<=N;i+=0.5) {
        for(int j=0;j<(int)i;j++) {
            p.y+=torDy[dir%4];
            p.x+=torDx[dir%4];
            if(!inRange(p.y,p.x)) break;
            if(board[p.y][p.x] != num) {
                if(num!=0) {
                    v.push_back(cnt);
                    v.push_back(num);
                }
                num = board[p.y][p.x];
                cnt = 1;
            }
            else cnt++;
        }
        dir++;
    }

    v.resize(N*N);

    p.y = N/2, p.x = N/2;
    dir = 0;
    int idx=0;
    for(double i=1.0;i<=N;i+=0.5) {
        for(int j=0;j<(int)i;j++) {
            p.y+=torDy[dir%4];
            p.x+=torDx[dir%4];
            if(!inRange(p.y,p.x)) break;
            board[p.y][p.x] = v[idx++];
        }
        dir++;
    }
}

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

    cin>>N>>M;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>board[i][j];

    point shark = {N/2,N/2};

    while(M--) {
        int d,s; cin>>d>>s;
        blizzard(shark,d-1,s);
        
        do{
            flag = false;
            sort(shark);
            boom(shark);
        }while(flag); // 폭파할 구슬이 없을 때까지
        
        change(shark);
    }
    
    cout<<marble[0]+2*marble[1]+3*marble[2];

    return 0;
}
0%