문제
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.
파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.
마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.
- 남아있는 얼음 A[r][c]의 합
- 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.
입력
첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.
풀이
처음에는 분할하여 하는 것을 생각하였지만 멍청한 생각이였다.
남아있는 얼음개수, 얼음 덩어리는 BFS로 간단하게 해결이 가능하지만, 움직이는걸 해결하는데 큰 시간이 걸렸다..
결론적으로 이동하는 규칙은 은근? 간단하였다.
L=1일때와 L=2일때 보면 행과 열에 따라 규칙을 가지고 이동하였다.
L에 따라 나눠진 조각을 보고 각장 1행,2행.. 1열,2열로 생각하면, 이동시 행은 열, 열은 2^l +1 -i 인 규칙을 가지고
있다.
즉 이렇게 표현이 가능하다.
행 -> 열, 열은 2^L + 1 -i, 주의 해야 하는 것은 나의 경우에는 temp_map에 저장 할 때 1,1로 그 나눠진 네모칸을 옮겨서 하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void rotate_map(int x, int y, int l) {
int len = (1 << l);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
temp_map[j][len + 1 - i] = map[x + i - 1][y + j - 1];
}
}
for (int i = 1; i <= len; i++) {
for (int j =1 ; j <= len; j++) {
map[x+i-1][y+j-1] = temp_map[i][j];
}
}
}
|
cs |
이동만 해결하면 문제는 매우 쉽다. 전체코드는 다음과 같다.
|
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
|
// 마법사 상어와 파이어스톰
#include <iostream>
#include <cmath>
#include <queue>
#include <utility>
#include <cstring>
#define MAX 64+2
using namespace std;
int N, Q;
int map[MAX][MAX];
int count_ = 0;
int temp_map[MAX][MAX];
int check[MAX][MAX];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int max_res = 0;
void BFS(int x,int y) {
check[x][y] = 1;
queue<pair<int, int>> q;
q.push(make_pair(x, y));
int count = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int next_x = x + dx[i];
int next_y = y + dy[i];
if (next_x >= 1 && next_x <= (1 << N) && next_y >= 1 && next_y <= (1 << N)) {
if (map[next_x][next_y] != 0 && check[next_x][next_y] == -1) {
check[next_x][next_y] = 1;
q.push(make_pair(next_x, next_y));
count++;
}
}
}
}
max_res = max(max_res, count);
}
void melt() {
queue<pair<int, int>> melt_space;
for (int i = 1; i <= (1 << N); i++) {
for (int j = 1; j <= (1 << N); j++) {
int count = 0;
if (map[i][j] == 0)
continue;
for (int k = 0; k < 4; k++) {
int next_x = i + dx[k];
int next_y = j + dy[k];
if (map[next_x][next_y] <= 0) {
count++;
}
}
if (count >= 2) {
melt_space.push(make_pair(i, j));
}
}
}
while (!melt_space.empty()) {
map[melt_space.front().first][melt_space.front().second]--;
melt_space.pop();
}
}
void rotate_map(int x, int y, int l) {
int len = (1 << l);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
temp_map[j][len + 1 - i] = map[x + i - 1][y + j - 1];
}
}
for (int i = 1; i <= len; i++) {
for (int j =1 ; j <= len; j++) {
map[x+i-1][y+j-1] = temp_map[i][j];
}
}
}
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
}
void input() {
cin >> N >> Q;
for (int i = 1; i <= (1 << N); i++) {
for (int j = 1; j <= (1 << N); j++) {
cin >> map[i][j];
}
}
}
void solve() {
for (int i = 0; i < Q; i++) {
int L;
cin >> L;
for (int j = 1; j <= (1 << N); j = j + (1 << L)) {
for (int k = 1; k <= (1 << N); k = k + (1 << L)) {
rotate_map(j, k, L);
}
}
melt();
}
int total_ans = 0;
memset(check, -1, sizeof(check));
for (int i = 1; i <= (1 << N); i++) {
for (int j = 1; j <= (1 << N); j++) {
total_ans += map[i][j];
if (check[i][j] == -1 && map[i][j] != 0) {
BFS(i, j);
}
}
}
cout << total_ans << endl;
cout << max_res << endl;
}
int main() {
init();
input();
solve();
}
|
cs |
훈수와 질문은 언제나 환영
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 17135] 캐슬 디펜스 (C++) (0) | 2021.08.16 |
|---|---|
| [백준 17140] 이차원 배열과 연산 (C++) (0) | 2021.08.13 |
| [백준 12100] 2048 (Easy) (C++) (0) | 2021.08.12 |
| [백준 16235] 나무 재테크 (C++) (0) | 2021.08.10 |
| [백준 17143] 낚시왕 (C++) (1) | 2021.08.10 |