백준 20058 마법사 상어와 파이어스톰
https://www.acmicpc.net/problem/20058
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
문제
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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가 순서대로 주어진다.
출력
첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.
제한
- 2 ≤ N ≤ 6
- 1 ≤ Q ≤ 1,000
- 0 ≤ A[r][c] ≤ 100
- 0 ≤ Li ≤ N
예제 입력 1
3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1
예제 출력 1
284 64
[풀이 과정]
1. q만큼 solve함수를 실행한다.
2. solve(int l, int n)
- l : 단계 L
- n : 격자의 크기
- l의 간격으로 rotate함수를 실행한다.
- rotate의 결과가 arr2에 저장되어 있으므로 update_arr함수를 활용해서 arr를 업데이트한다.
- 얼음이 있는 칸이 3개 이상 인접해있는지 확인하기 위해 melt_ice함수를 실행한다.
- melt_ice의 결과값이 3미만이면 arr2의 해당 위치값을 1 감소시킨다.
- update_arr함수로 arr값을 업데이트한다.
3. rotate(int x, int y, int cnt)
- cnt : 회전시킬 칸의 크기(2의 L제곱)
- 조건에 맞게 시계방향으로 회전시킨다.
- 이때 반복문 k를 쓰는 이유는 아래와 같이 cnt/2번 회전을 해야 하기 때문이다.
(cnt가 4일때, 2번 회전)
| o | o | o | o |
| o | o | ||
| o | o | ||
| o | o | o | o |
| o | o | ||
| o | o | ||
- b += 2를 한 이유는 큰 네모에서 안쪽 네모로 이동할 때 크기가 2씩 감소하기 때문에 각 반복문에서 a-b를 해줬다.
4. melt_ice(int x, int y, int N)
- 현재위치의 상하좌우를 확인하면서 범위 내에 있고 얼음이 있는 칸이면 cnt를 1증가시킨다.
- 최종 cnt를 return 한다.
5. q만큼 회전과 얼음이 녹는 과정이 끝났다면 가장 큰 덩어리의 크기를 구하기 위해 탐색을 한다.
- 전체를 탐색하면서 방문 전이고 0보다 큰 값이면 check_ice함수를 실행한다.
- check_ice에서 받은 res값을 v 벡터에 push한다.
- 모든 덩어리의 크기를 구했으면 sort함수를 통해 그중에 가장 큰 값을 찾는다.
- 만약 v의 사이즈가 0이면 덩어리의 크기는 0이다.
- 전체 ice의 총합과 덩어리 크기의 최댓값을 출력한다.
6. check_ice(int a, int b, in N)
- 이동 가능한 모든 곳을 방문하면서 ice에 위치를 저장한다.
- 탐색이 끝났으면 ice의 크기를 확인한다.
- 이때 ice의 크기가 3미만이라면 해당 위치의 값을 1감소시킨다.
- ice의 크기를 return한다.
[소스 코드]
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 100;
int n, q, arr[MAX][MAX], arr2[MAX][MAX];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
bool visited[MAX][MAX];
void rotate(int x, int y, int cnt) {
int a = cnt - 1, b = 0;
for (int k = 0; k < cnt / 2; k++) {
for (int i = 0; i < a - b; i++) arr2[x + k][y + a - i - k] = arr[x + i + k][y + k];
for (int i = 0; i < a - b; i++) arr2[x + a - i - k][y + a - k] = arr[x + k][y + a - i - k];
for (int i = 0; i < a - b; i++) arr2[x + a - k][y + i + k] = arr[x + a - i - k][y + a - k];
for (int i = 0; i < a - b; i++) arr2[x + i + k][y + k] = arr[x + a - k][y + i + k];
b += 2;
}
}
void update_arr(int N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) arr[i][j] = arr2[i][j];
}
}
int check_ice(int a, int b, int N) {
queue <pair<int, int> > q;
queue <pair<int, int> > ice;
q.push(make_pair(a, b));
ice.push(make_pair(a, b));
visited[a][b] = true;
int cnt = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (!visited[nx][ny] && arr[nx][ny] > 0) {
visited[nx][ny] = true;
cnt++;
q.push(make_pair(nx, ny));
ice.push(make_pair(nx, ny));
}
}
}
if (ice.size() >= 3) return ice.size();
while (!ice.empty()) {
int x = ice.front().first;
int y = ice.front().second;
ice.pop();
arr2[x][y]--;
}
return ice.size();
}
int melt_ice(int x, int y, int N) {
int cnt = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (arr[nx][ny] > 0) cnt++;
}
return cnt;
}
void solve(int l, int N) {
int cnt = pow(2, l);
for (int i = 0; i < N; i += cnt) {
for (int j = 0; j < N; j += cnt) rotate(i, j, cnt);
}
update_arr(N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr2[i][j] == 0) continue;
int adj = melt_ice(i, j, N);
if (adj < 3) arr2[i][j]--;
}
}
update_arr(N);
}
int main() {
scanf("%d %d", &n, &q);
int N = pow(2, n);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &arr[i][j]);
arr2[i][j] = arr[i][j];
}
}
for (int Q = 0; Q < q; Q++) {
int l_size;
scanf("%d", &l_size);
solve(l_size, N);
}
vector<int> v;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j] && arr[i][j] > 0) {
int res = check_ice(i, j, N);
v.push_back(res);
}
}
}
int max_val = 0;
if (v.size() > 0) {
sort(v.begin(), v.end(), greater<int>());
max_val = v[0];
}
int total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) total += arr[i][j];
}
printf("%d\n%d\n", total, max_val);
return 0;
}