https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
지금까지 푼 문제중에 제일 오래 걸리고 제일 많이 틀린 문제이다.. 나에게 좌절감을 준 문제.
내가 잘못 생각한 부분이 있었는데, 이 생각을 고치지 않아서 계속해서 틀린것이다.
나는 이 방식으로 진행했다.
1. N*N 맵을 일자로 핀다, 그 네모난 맵에는 들린 순서대로 1,2,3,,,, N*N -1 숫자를 부여한다.
2. 그리고 마법을 일으킨다. 이때 마법이 일어나면 아까 초기맵에 들린 순서대로 숫자를 부여 했으므로, 일자로 펼친 맵의 몇번쨰 index를 삭제하는지 알 수 있다.
3. 그 다음은 블럭을 터트린다. 이떄 일자 맵에 있는 것을 deque를 이용해 (횟수,숫자) 이 양식을 지켜 만든다.
터트린 블록은 제외한다.(터트린 블럭은 index를 알고 잇으므로, index가 같은 거는 그냥 continue)
4. 그리고 점수를 얻는 과정이다.
우선 주의해야할게 많다. 나는 기존에 터트리자마자 배열을 앞으로 이동, 또 숫자가 겹치면 터트리게 하였다.
하지만 문제를 보면, 모두 터트리고 난 뒤에 다시 숫자를 움직이는 것을 알 수 있었다..
5. 그 다음에는 맵을 다시 일자로 만들어준다, 이 경우는 위에 횟수 숫자로 해놨기 때문에 쉽다.
|
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
|
// 마법사 상어와 블리자드 21611번
#include <iostream>
#include <vector>
#include <utility>
#include <deque>
#define MAX 50
using namespace std;
int N, M;
// ↑, ↓, ←, →
int pop_dx[5] = { 0,-1,1,0,0 };
int pop_dy[5] = { 0,0,0,-1,1 };
// ←, ↓, →, ↑ 일짜로 피는 과정
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int MAP[MAX][MAX];
vector<pair<int, int>> operation;
// 처음부터 맵을 피고, 저렇게 할 때만 맵을 새로 만든다 그리고 다시 벡터로 맵 만들고
deque<pair<int, int>> map_1;
deque<int> map_2;
deque<int> magic_pop;
int total_count = 0;
void turn(int& x, int& y, int& dir, int& index, int& count) {
for (int i = 0; i < index; i++) {
x += dx[dir];
y += dy[dir];
if (MAP[x][y] == 0) {
MAP[x][y] = count++;
}
else {
map_2.push_back(MAP[x][y]);
MAP[x][y] = count++;
}
}
dir += 1;
if (dir == 4)
dir = 0;
}
void make_in_a_row() {
// map2 만들고, MAP을 순서에 따라 index
int x = N / 2 + 1;
int y = N / 2 + 1;
int dir = 0;
int index = 1;
int count = 1;
map_2.push_back(0);
while (x != 1 || y != 1) {
if (index == N - 1) {
turn(x, y, dir, index, count);
turn(x, y, dir, index, count);
turn(x, y, dir, index, count);
}
else {
turn(x, y, dir, index, count);
turn(x, y, dir, index, count);
index++;
}
}
}
void pop_marble() {
for (int i = 0; i < map_2.size(); i++) {
if (!magic_pop.empty() && i == magic_pop.front()) {
magic_pop.pop_front();
continue;
}
if (map_2[i] == 0)
map_1.push_back(make_pair(0, 0));
else if (map_1.back().second == map_2[i])
map_1.back().first++;
else
map_1.push_back(make_pair(1, map_2[i]));
}
map_2.clear();
magic_pop.clear();
bool flag = false;
while (flag == false) {
deque<pair<int, int>> temp;
flag = true;
temp.push_back(map_1.front());
map_1.pop_front();
while (!map_1.empty()) {
if (map_1.front().first >= 4) {
total_count += map_1.front().first * map_1.front().second;
map_1.pop_front();
flag = false;
continue;
}
if (temp.back().second == map_1.front().second) {
temp.back().first += map_1.front().first;
map_1.pop_front();
continue;
}
temp.push_back(map_1.front());
map_1.pop_front();
}
map_1 = temp;
}
int count = 0;
for (auto i : map_1) {
if (i.first == 0) {
map_2.push_front(0);
continue;
}
if (count == N * N - 1) {
break;
}
map_2.push_back(i.first);
map_2.push_back(i.second);
count += 2;
}
map_1.clear();
}
void magic(const int& dir, const int& size) {
int x = N / 2 + 1;
int y = N / 2 + 1;
for (int i = 0; i < size; i++) {
x += pop_dx[dir];
y += pop_dy[dir];
magic_pop.push_back(MAP[x][y]);
}
}
void solve() {
make_in_a_row();
for (auto i : operation) {
magic(i.first, i.second);
pop_marble();
}
cout << total_count << endl;
}
void input() {
cin >> N >> M;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
cin >> MAP[i][j];
for (int i = 1; i <= M; i++) {
int dir, size;
cin >> dir >> size;
operation.push_back(make_pair(dir, size));
}
}
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
}
int main() {
init();
input();
solve();
}
|
cs |
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 13164] 행복 유치원 (C++) (0) | 2021.08.27 |
|---|---|
| [백준 11000] 강의실 배정 (C++) (0) | 2021.08.27 |
| [백준 20061] 모노미노도미노 2 (C++) (0) | 2021.08.23 |
| [백준 21609] 상어 중학교 (C++) (0) | 2021.08.22 |
| [백준 14499] 주사위 굴리기 (C++) (0) | 2021.08.21 |