문제
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2^N × 2^N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (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] 이다.
마지막 줄에는 마법사 상어가 시전한 단계 L_1, L_2, ..., L_Q가 순서대로 주어진다.
출력
첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.
문제 풀이
1. 2^N × 2^N 블록 단위 회전
- 전체 맵을 2^L 크기로 나눈 뒤 각 블록을 시계 방향 90도 회전
- (0, 0) -> (0, 1)
- (0, 1) -> (1, 1)
- (1, 0) -> (0, 0)
- (1, 1) -> (1, 0)
- 이므로 회전 시,
회전한 x 값 = 이전 y값,회전한 y 값 = 전체 크기 - 이전 x값 - 1이 된다.
즉,map[x][y] = map[y][n-1-x]
- 새로운 배열에 결과를 저장 후 map 갱신
static void splitMap(int level) {
int step = 1 << level;
int[][] newMap = new int[size][size];
for (int i = 0; i < size; i += step) {
for (int j = 0; j < size; j += step) {
for (int x = 0; x < step; x++) {
for (int y = 0; y < step; y++) {
// (x, y) → (y, step-1-x)
newMap[i + y][j + step - 1 - x] = map[i + x][j + y];
}
}
}
}
map = newMap;
}
2. 얼음 감소
- 각 칸에서 상하좌우 인접한 얼음 개수 확인
- 3개 미만이면 해당 칸의 얼음
-1
static void melt() {
int[][] temp = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int cnt = 0;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= size || ny >= size)
continue;
if (map[nx][ny] > 0)
cnt++;
}
if (map[i][j] > 0 && cnt < 3) {
temp[i][j] = map[i][j] - 1;
} else {
temp[i][j] = map[i][j];
}
}
}
map = temp;
}
3. 남아있는 얼음의 합 구하기
map의 값이 0이상인 값을 모두 합한다.
static int getTotalIce() {
int sum = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (map[i][j] <= 0)
continue;
sum += map[i][j];
}
}
return sum;
}
4. 가장 큰 얼음 덩어리 구하기
BFS를 통해 인접 노드를 돌며, 0보다 큰 값으로 이뤄진 얼음의 가장 큰 덩어리를 구한다.
static int getMaxBlock() {
int maxBlock = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (map[i][j] > 0) {
maxBlock = Math.max(bfs(i, j), maxBlock);
}
}
}
return maxBlock;
}
static boolean[][] visited;
static int bfs(int x, int y) {
int cnt = 1;
Queue<int[]> queue = new ArrayDeque<int[]>();
queue.add(new int[] { x, y });
visited = new boolean[size][size];
visited[x][y] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
x = curr[0];
y = curr[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || ny < 0 || nx >= size || ny >= size)
continue;
if (!visited[nx][ny] && map[nx][ny] > 0) {
visited[nx][ny] = true;
queue.offer(new int[] { nx, ny });
cnt++;
}
}
}
return cnt;
}
전체코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] map;
static int N, Q, size;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
N = Integer.parseInt(split[0]);
Q = Integer.parseInt(split[1]);
size = 1 << N;
map = new int[size][size];
for (int i = 0; i < size; i++) {
split = br.readLine().split(" ");
for (int j = 0; j < size; j++) {
map[i][j] = Integer.parseInt(split[j]);
}
}
String[] Level = br.readLine().split(" ");
for (String L : Level) {
int level = Integer.parseInt(L);
splitMap(level);
melt();
}
System.out.println(getTotalIce());
System.out.println(getMaxBlock());
}
static int[] dx = { 0, -1, 0, 1 };
static int[] dy = { 1, 0, -1, 0 };
static void splitMap(int level) {
int step = 1 << level;
int[][] newMap = new int[size][size];
for (int i = 0; i < size; i += step) {
for (int j = 0; j < size; j += step) {
for (int x = 0; x < step; x++) {
for (int y = 0; y < step; y++) {
newMap[i + y][j + step - 1 - x] = map[i + x][j + y];
}
}
}
}
map = newMap;
}
static void melt() {
int[][] rotated = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int cnt = 0;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (nx < 0 || ny < 0 || nx >= size || ny >= size) {
continue;
}
if (map[nx][ny] > 0) {
cnt++;
}
}
if (map[i][j] > 0 && cnt < 3) {
rotated[i][j] = map[i][j] - 1;
} else {
rotated[i][j] = map[i][j];
}
}
}
map = rotated;
}
static int getTotalIce() {
int sum = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (map[i][j] <= 0)
continue;
sum += map[i][j];
}
}
return sum;
}
static int getMaxBlock() {
int maxBlock = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (map[i][j] > 0) {
maxBlock = Math.max(bfs(i, j), maxBlock);
}
}
}
return maxBlock;
}
static boolean[][] visited;
static int bfs(int x, int y) {
int cnt = 1;
Queue<int[]> queue = new ArrayDeque<int[]>();
queue.add(new int[] { x, y });
visited = new boolean[size][size];
visited[x][y] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
x = curr[0];
y = curr[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || ny < 0 || nx >= size || ny >= size)
continue;
if (!visited[nx][ny] && map[nx][ny] > 0) {
visited[nx][ny] = true;
queue.offer(new int[] { nx, ny });
cnt++;
}
}
}
return cnt;
}
}
링크
'알고리즘' 카테고리의 다른 글
| [코드트리 - L12] 25년 하반기 오전 1번 문제 - 택배 하차 (0) | 2026.04.07 |
|---|---|
| [알고리즘] 시간 복잡도 & 공간 복잡도 (0) | 2026.04.05 |
| [MySQL] 자주 쓰이는 함수 정리 (0) | 2026.03.27 |
| [백준 - G3] 20057. 마법사 상어와 토네이도 (0) | 2026.03.26 |
| [알고리즘] Java에서의 정렬 방법(Comparable, Comparator) (0) | 2026.03.22 |