알고리즘/문제풀이
[백준/BOJ] 20058 마법사 상어와 파이어스톰 - JAVA
LIRI
2025. 7. 1. 20:20
[백준/BOJ] 20058 마법사 상어와 파이어스톰 - JAVA
문제
https://www.acmicpc.net/problem/20058
문제 분석
조건
`(2N)×(2N)` 크기의 격자에 각 칸의 얼음의 양이 주어진다. Q번의 파이어스톰을 시전할때 한번의 파이어스톰은 아래 과정을 거친다.
1. 전체 격자를 `(2L)×(2L)`크기의 부분격자로 나누고 모든 부분격자는 시계 방향으로 90도 회전한다.
2. 상하좌우로 인접한 칸에 얼음이 있는 칸이 3개 미만이면 해당 칸의 얼음의 양이 1 줄어든다.
Q번의 파이어스톰을 모두 시전한 후, 전체 격자에 남아있는 얼음의 총량과 가장 큰 얼음 덩어리가 차지하는 칸의 개수를 출력하는 문제이다.
풀이방법
단순 구현문제로 부분적으로 격자를 회전시키고 얼음을 녹이는 것을 구현하였다. 남은 얼음 양의 합을 따로 구하지 않고, 격자를 입력받을 때 총 얼음의 양을 구하였고, 얼음의 양이 줄때마다 총 얼음의 양을 같이 감소시켰다.
얼음의 양을 감소 시키는 부분에서는 격자를 탐색하며 바로 양을 줄이는 것이 아니라 좌표를 리스트에 넣고 양을 줄이도록 하였다. 그 이유는 아래처럼 격자칸에 얼음이 남아있을때 좌표를 하나씩 탐색하며 감소시킬 경우, 이미 녹아 버린 값을 참조하여 감소하면 안되는 좌표가 감소하게 될 수도 있기때문이다.
아래처럼 2번이 들어있는 격자칸은 얼음이 감소하면 안되는 칸이지만 순차적으로 확인 후 바로 감소를 진행하게 된다면 오른쪽처럼 감소된 후의 값을 참고하게 되어 얼음양이 감소할 수 있다.
X 1 X x 0 x
1 2 1 ---> 0 1
X 5 6코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int[][] map;
static int mapSize;
static int bigIceSize = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int remainIce = 0;
int N = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
mapSize = (int) Math.pow(2, N);
map = new int[mapSize][mapSize];
for (int r = 0; r < mapSize; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < mapSize; c++) {
map[r][c] = Integer.parseInt(st.nextToken());
remainIce += map[r][c]; // 초기 얼음 양 계산
}
}
st = new StringTokenizer(br.readLine());
for (int q = 0; q < Q; q++) {
// 격자 부분 회전
int L = Integer.parseInt(st.nextToken());
int splitSize = (int) Math.pow(2, L);
for (int r = 0; r < mapSize; r += splitSize) {
for (int c = 0; c < mapSize; c += splitSize) {
rotateArea(r, c, splitSize);
}
}
// ice--
List<int[]> declineList = new ArrayList<>();
for (int r = 0; r < mapSize; r++) {
for (int c = 0; c < mapSize; c++) {
if (map[r][c] == 0) {
continue;
}
if (isDecline(r, c)) { // 주위 얼음이 있는 칸이 3칸 미만인지 확인
declineList.add(new int[]{r, c}); // 미리 감소시키면 안됨
}
}
}
for (int[] pos : declineList) { // 얼음의 양은 동시 감소
map[pos[0]][pos[1]]--;
remainIce--; // 남은 얼음 양 계산
}
}
// 얼음 덩어리 크기 계산
for (int r = 0; r < mapSize; r++) {
for (int c = 0; c < mapSize; c++) {
if (map[r][c] > 0) {
bigIceSize = Math.max(bigIceSize, bfs(r, c));
}
}
}
System.out.println(remainIce);
System.out.println(bigIceSize);
}
/**
* 구역의 크기 계산
*
* @return 얼음 덩어리 크기
*/
private static int bfs(int r, int c) {
int areaCount = 0;
map[r][c] = 0;
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{r, c});
while (!queue.isEmpty()) {
areaCount++;
int[] now = queue.poll();
for (int[] dir : dirs) {
int nextR = now[0] + dir[0];
int nextC = now[1] + dir[1];
if (isInvalid(nextR, nextC)) {
continue;
}
if (map[nextR][nextC] > 0) {
queue.add(new int[]{nextR, nextC});
map[nextR][nextC] = 0;
}
}
}
return areaCount;
}
/**
* 얼음이 감소하는지 확인
*
* @return 감소해야되면 true
*/
private static boolean isDecline(int r, int c) {
int noIceCount = 0; // 얼음이 없는 인접구역 카운트
for (int[] dir : dirs) {
if (noIceCount > 1) { // 인접한 곳에 얼음이 없는 칸이 2칸 이상이면 감소함
return true;
}
int newR = r + dir[0];
int newC = c + dir[1];
if (isInvalid(newR, newC)) { // 격자 밖도 없음이 없음
noIceCount++;
continue;
}
if (map[newR][newC] == 0) {
noIceCount++;
}
}
return noIceCount > 1;
}
private static boolean isInvalid(int r, int c) {
return r < 0 || c < 0 || r >= mapSize || c >= mapSize;
}
/**
* 격자 회전
*
* @param sr 격자 시작 좌표
* @param sc
* @param splitSize 격자 크기
*/
private static void rotateArea(int sr, int sc, int splitSize) {
int[][] temp = new int[splitSize][splitSize];
// 회전 후 임시 배열에 대입
for (int r = 0; r < splitSize; r++) {
for (int c = 0; c < splitSize; c++) {
temp[c][splitSize - 1 - r] = map[sr + r][sc + c];
}
}
for (int r = 0; r < splitSize; r++) {
for (int c = 0; c < splitSize; c++) {
map[sr + r][sc + c] = temp[r][c];
}
}
}
}728x90