문제 URL : https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
문제접근법 :
시뮬레이션 문제입니다.
3가지의 행동을 구현해야하는데
첫번째 : 마법시전
두번째 : 구슬폭발
세번째 : 구슬변화
총 M번동안 이3가지를 계속 반복하는겁니다.
그러기전에
가장 처음으로 해야하는것이 달팽이 알고리즘인데 3가지를 달팽이 알고리즘없이 할려면 매우 힘들게 구현해야하며
달팽이 알고리즘을 사용함으로 n*n의 2차원 행렬을
n*n사이즈의 1차원 행렬로 만들어야 합니다.
달팽이 알고리즘은 회오리모양처럼 탐색하는 순서를 정합니다. 하지만 전 달팽이알고리즘을 다른문제에서
얘기한적이 있습니다.
https://congsoony.tistory.com/69?category=993889
LeetCode 59 Spiral Matrix II
문제 URL : leetcode.com/problems/spiral-matrix-ii/ 문제 접근법 : 기초적인 달팽이 알고리즘 문제입니다. c언어를 처음 접했을때 반복문 사용을 배우고나면 풀게되는 문제였었는데 그렇기 때문에 반복문을
congsoony.tistory.com
이글을 참고해주시기 바랍니다.
그렇다면 달팽이알고리즘을 이용해서 해당 순서의 좌표를 저장한후 가장 중앙에있는 상어는 필요없으니 해당 좌표 하나만 제거하면 그사이즈는 n*n -1 이 됩니다. 그리고 중아에서부터 바깥으로 나가는 순서이니 순서를 다시 거꾸로 해주면
원하는 순서가 됩니다.
그때부터 이전에 얘기한 m번의 총 3가지 행동을 반복하는겁니다.
저는 좌표를 0,0 ~ n-1,n-1로 사용하였기에 이좌표로 생각해주세요
첫번째 : 마법시전은 n/2,n/2에서 시작해서 해당 거리만큼 해당방향에 2차원 행렬을 모든 수를 전부 제거합니다. 즉 0으로 만들죠
두번째 : 두번째 구슬이 폭발해야하는데 구슬을 앞당기기 위해선 달팽이 알고리즘에서 사용했던 좌표를 탐색하면서 0이 아닌 숫자들을 하나의 1차원 배열에 저장합니다. c++에선 vector를 사용하는것이 가장편하죠 전부 담았으면 하나로 이어진겁니다. 그리고 연속된 4개수가 있는지 확인합니다.
-> 여기서 주의할점은 4개이상의 구슬이 동시에 폭발해야하는 점입니다. 만약 4개이상있고 왼쪽방향이든, 오른쪽방향이든 순차적으로 폭발하게 된다면 1111222211 일경우 전부 폭발할수있는 치명적인 오류가 생기기때문에 반드시 동시에 폭발하는 연출을 구현해야합니다. 그러면 마지막 11만 남게되겠죠
그리고 마지막 세번째 : 연속된 구슬들을 하나의 그룹이고 그그룹의 소속된 구슬 개수 A 그구슬의 번호B라 할때
항상 2개의 구슬로 만들어집니다.
쉽게얘기하면 111 이라는 구슬이있을때 연속된게 이그룹은 1이 3개(A) 이고, 구슬의 번호는 1이니까
최종적으로 31이 된다는 얘기입니다.
이런식으로 구현하면됩니다.
폭발을 할때 구슬이 하나도 안남게 되는경우가 있으니 그것도 주의해주시기 바랍니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
#define pii pair<int,int>
int dy[5] = { 0,-1,1,0,0 };
int dx[5] = { 0,0,0,-1,1 };
vvi board;
v<pii> mv, sv;
vi bv;
int n, m;
int res[10];
void input() {
cin >> n >> m;
board = vvi(n, vi(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
}
}
mv = v<pii>(m);
for (int i = 0; i < m; i++)
cin >> mv[i].first >> mv[i].second;
}
void snail() { //달팽이알고리즘
int cnt = 0;
int y = -1, x = -1;
vvi arr(n, vi(n));
while (cnt < n * n) {
for (y++, x++; x < n && arr[y][x] == 0; x++) {
arr[y][x] = ++cnt;
sv.push_back({ y,x });
}
for (y++, x--; y < n && arr[y][x] == 0; y++) {
arr[y][x] = ++cnt;
sv.push_back({ y,x });
}
for (y--, x--; x >= 0 && arr[y][x] == 0; x--) {
arr[y][x] = ++cnt;
sv.push_back({ y,x });
}
for (y--, x++; y >= 0 && arr[y][x] == 0; y--) {
arr[y][x] = ++cnt;
sv.push_back({ y,x });
}
}
sv.pop_back();//마지막은 n/2,n/2 인 상어가 있는 좌표니 필요없으니 제거
reverse(sv.begin(), sv.end());//순서반대
}
void magic(int dir,int s) {
int y = n / 2;
int x = n / 2;
for (int i = 1; i <= s; i++) { //마법시전
int ny = y + dy[dir] * i;
int nx = x + dx[dir] * i;
board[ny][nx] = 0;
}
}
void explode() {
bv.clear();
for (auto [y, x] : sv) {//달팽이 순서에서 해당 구슬들을 1차원 벡터에 집어넣음
if (board[y][x])
bv.push_back(board[y][x]);
}
//구슬폭발
while (true) {
bool flag = true;
int cnt = 1;
if (bv.empty())return;//구슬이 하나도없는경우
vi temp = { bv[0] };
for (int i = 1; i < bv.size(); i++) {
if (temp.back() == bv[i])
cnt++;
else {
if (cnt >= 4) {//4개이상있는지
flag = false;
res[temp.back()] += cnt;//폭발한 구슬이 ㅕ
while (cnt--)temp.pop_back();
}
cnt = 1;
}
temp.push_back(bv[i]);
}
if (cnt >= 4&&!temp.empty()) {//마지막에도 4개이상이었는지 확인
flag = false;
res[temp.back()] += cnt;
while (cnt--)temp.pop_back();
}
bv = temp;
if (flag)break;//한번이라도 폭발된적이없으면 더이상 폭발하지않음
}
}
void change() { //구슬 A, B로 변화
if (bv.empty())return;
int before = bv[0];
int cnt = 1;
vi temp;
for (int i = 1; i < bv.size(); i++) {
if (before == bv[i])
cnt++;
else {
temp.push_back(cnt);
temp.push_back(before);
cnt = 1;
}
before = bv[i];
}
temp.push_back(cnt);
temp.push_back(before);
board = vvi(n, vi(n));
for (int i = 0; i < sv.size() && i < temp.size(); i++)
board[sv[i].first][sv[i].second] = temp[i];
}
void solve() {
snail();
for (int i = 0; i < m; i++) {
magic(mv[i].first,mv[i].second);
explode();
change();
}
cout << res[1] + 2 * res[2] + 3 * res[3] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 13911 집 구하기 (0) | 2022.07.31 |
|---|---|
| 백준 19237 어른 상어 (0) | 2022.07.21 |
| 백준 16681 등산 (0) | 2022.07.13 |
| 백준 11952 좀비 (0) | 2022.07.13 |
| 백준 14461 소가 길을 건너간 이유 7 (0) | 2022.07.13 |
