[백준 20058번] 마법사 상어와 파이어스톰 (Java)

> 자바, 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

📖 문제 : 마법사 상어와 파이어스톰 (Java)

 

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전	L = 1	L = 2

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

 

입력

첫째 줄에 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

 

예제 입력 2 

3 2
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 2

예제 출력 2 

280
64

 

 

내 코드

package a_samsung;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_20058_마법사상어와파이어스톰 {

  static int N, Q, L, mapSize;
  static int[][] map;
  static int[] dy = new int[] { -1, 0, 1, 0 };
  static int[] dx = new int[] { 0, 1, 0, -1 };
  static int iceSum = 0;
  static int iceCnt = 0;

  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    Q = Integer.parseInt(st.nextToken());

    mapSize = (int) Math.pow(2, N);
    map = new int[mapSize][mapSize];

    for (int i = 0; i < mapSize; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < mapSize; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < Q; i++) {
      L = Integer.parseInt(st.nextToken());
      iceCnt = 0;
      if (L == 0) {
        L = 1;
      } else {
        L = (int) Math.pow(2, L);
      }

      map_change();

      melt_ice();

      find_ice();

    }
    System.out.println(iceSum);
    System.out.println(iceCnt);
  }

  static void find_ice() {
    boolean[][] visit = new boolean[mapSize][mapSize];

    for (int i = 0; i < mapSize; i++) {
      for (int j = 0; j < mapSize; j++) {
        if (visit[i][j])
          continue;
        if (map[i][j] > 0) {
          Queue<int[]> queue = new ArrayDeque<>();
          queue.offer(new int[] { i, j });
          visit[i][j] = true;
          int cnt = 1;
          while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cy = current[0];
            int cx = current[1];

            for (int k = 0; k < 4; k++) {
              int yy = cy + dy[k];
              int xx = cx + dx[k];
              if (yy < 0 || xx < 0 || yy > mapSize - 1 || xx > mapSize - 1 || visit[yy][xx])
                continue;

              if (map[yy][xx] > 0) {
                visit[yy][xx] = true;
                queue.offer(new int[] { yy, xx });
                cnt += 1;
              }
            }
          }

          iceCnt = Math.max(iceCnt, cnt);
        }
      }
    }

  }

  static void melt_ice() {
    int[][] new_map = new int[mapSize][mapSize];
    int sum = 0;

    for (int y = 0; y < mapSize; y++) {
      for (int x = 0; x < mapSize; x++) {

        int iceCnt = 0;

        for (int i = 0; i < 4; i++) {
          int yy = y + dy[i];
          int xx = x + dx[i];

          if (0 > yy || 0 > xx || yy > mapSize - 1 || xx > mapSize - 1)
            continue;

          if (map[yy][xx] > 0)
            iceCnt += 1;

        }

        if (iceCnt < 3) {
          if (map[y][x] == 0) {
            new_map[y][x] = 0;
          } else {
            new_map[y][x] = map[y][x] - 1;
          }

        } else {
          new_map[y][x] = map[y][x];
        }
        sum += new_map[y][x];
      }

    }
    for (int i = 0; i < mapSize; i++) {
      map[i] = new_map[i].clone();
    }
    iceSum = sum;

  }

  static void map_change() {

    for (int i = 0; i < mapSize / L; i++) {
      for (int j = 0; j < mapSize / L; j++) {
        int[] tempIce = new int[L * L];
        int startY = i * L;
        int startX = j * L;
        int idx = 0;

        for (int y = startY; y < startY + L; y++) {
          for (int x = startX; x < startX + L; x++) {
            tempIce[idx] = map[y][x];

            idx += 1;
          }
        }

        idx = 0;
        for (int x = startX + L - 1; x >= startX; x--) {
          for (int y = startY; y < startY + L; y++) {
            map[y][x] = tempIce[idx];
            idx += 1;
          }
        }

      }

    }

  }
}

 

 

 

 

백준

https://www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰