[백준] 21610. 마법사 상어와 비바라기 (Java)

21610. 마법사 상어와 비바라기

21610번: 마법사 상어와 비바라기

---

아이디어💡

상어 시리즈는 공통적으로 문제를 잘 읽고 제대로 구현하는걸 요구합니다.

따라서 다음과 같이 진행했습니다.

1. 초기 설정
   맵과 구름의 생성: N×N 크기의 맵과 초기 구름 위치가 설정됩니다. 구름은 특정 위치에 생성되며, 이후 이동, 비 내리기, 물 복사 버그 마법 등의 과정을 거치게 됩니다.
2. 구름의 이동
   방향과 속도: 사용자로부터 입력 받은 방향(d)과 속도(s)에 따라 구름이 이동합니다. 이때, 구름의 위치는 모듈로 연산을 통해 경계를 넘어가는 경우를 처리합니다.
3. 비 내리기
   구름이 있는 위치에 비가 내려, 그 칸의 물의 양이 증가합니다.
4. 물 복사 버그 마법
   구름이 있는 칸 기준으로 대각선 방향에 물이 있는 바구니의 수만큼 해당 칸의 물의 양이 증가합니다. 경계를 넘어가는 칸은 처리하지 않습니다.
5. 구름 생성
   물의 양이 2 이상인 칸에서 구름이 새로 생성됩니다. 단, 이번 턴에 구름이 사라진 자리는 제외합니다.
6. 결과 계산
   모든 과정이 끝난 후, 맵에 있는 물의 총량을 계산합니다.

특징 및 아이디어

• 모듈로 연산의 활용: 구름의 이동은 맵의 경계를 넘어갈 수 있기 때문에, 모듈로 연산을 통해 이를 간단하게 처리합니다.
• 마킹 기법: 구름이 사라진 자리를 구별하기 위해, 물의 양을 음수로 전환하는 방식을 사용합니다. 이후 구름 생성 단계에서 이를 확인하여 새 구름이 생성되지 않도록 합니다.
• 물 복사 버그 마법의 구현: 대각선 방향으로 물이 있는 바구니를 확인하고, 그 수만큼 현재 칸의 물의 양을 증가시키는 로직으로 구현됩니다.

---

시간복잡도⌛

• 맵 채우기: N×N 크기의 맵을 채우는 데 O(N^2)의 시간이 걸립니다.
• M번의 이동 명령 처리:
  • 각 이동 명령에 대해 구름 이동, 비 내리기, 물복사 버그 마법, 새 구름 생성 등의 연산이 수행됩니다.
  • 구름 이동 및 비 내리기: 구름의 수를 C라고 할 때, 최악의 경우 모든 칸에 구름이 있을 수 있으므로 O(N^2)의 시간이 걸릴 수 있습니다.
  • 물복사 버그 마법: 구름이 있는 각 칸에 대해 대각선 4방향을 확인하므로, 이 부분은 구름 당 O(1)의 시간이 소요됩니다. 따라서 최악의 경우 O(N^2)입니다.
  • 새 구름 생성: 전체 맵에 대해 검사하므로 O(N^2)의 시간이 걸립니다.
• 물의 양 합 구하기: 전체 맵에 대해 합을 구하는 연산이므로 O(N^2)의 시간이 걸립니다.
  최종적으로, 이 프로그램의 시간 복잡도는 각 이동 명령 처리가 O(N^2)이며, M번의 이동 명령이 주어지므로 총 시간 복잡도는 O(M*N^2)

---

소스코드🧑‍💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
  static int N; // 맵 크기
  static int[][] arr; // 맵
  static int[] dx = {0, 0,-1,-1,-1,0,1,1,1}; // 방향 (하나씩 더 추가)
  static int[] dy = {0, -1,-1,0,1,1,1,0,-1};
  static List<Cloud> clouds = new ArrayList<>(); // 구름
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    arr = new int[N][N];
    // 맵 채우기
    for(int i=0; i<N; i++) {
      st = new StringTokenizer(br.readLine());
      for(int j=0; j<N; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    // 최초 구름
    clouds.add(new Cloud(N-1, 0));
    clouds.add(new Cloud(N-1, 1));
    clouds.add(new Cloud(N-2, 0));
    clouds.add(new Cloud(N-2, 1));

    for(int i=0; i<M; i++) {
      st = new StringTokenizer(br.readLine());
      int d = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      for(Cloud cloud : clouds) {
        cloud.move(d, s); // 1. 구름 이동
        cloud.rain(); // 2. 비가 내린다 주륵주륵
      }
      for(Cloud cloud : clouds) {
        cloud.waterCopyBug(); // 4. 물복사버그 마법 시전
        cloud.stamp(); // 구름이 있던자리라고 표시하기
      }
      clouds = new ArrayList<>(); // 구름 삭제(물복사를 먼저 처리하는게 더 편리해서 순서 바꿈)
      generateClouds(); // 구름 발생
    }
    System.out.println(calcSum());
  }
  /**
   * 물의 양 합 구하기
   */
  static int calcSum() {
    int sum = 0;
    for(int[] a : arr) {
      sum += Arrays.stream(a).sum();
    }
    return sum;
  }

  /**
   * 구름 만들기
   * 1. 물의 양이 2 이상인 칸만
   * 2. 해당 이동에서 구름이 있던 자리는 제외
   */
  static void generateClouds() {
    for(int i=0; i<N; i++) {
      for(int j=0; j<N; j++) {
        // 구름이 있던 자리는 원상복구만 시키기
        if(arr[i][j] < 0) {
          arr[i][j] = -arr[i][j];
        } else if (arr[i][j] >= 2) { // 2 이상인 칸에 구름 생기기
          arr[i][j] -= 2; // 물의 양 2 줄어들기
          clouds.add(new Cloud(i, j));
        }
      }
    }
  }
  /**
   * 구름
   */
  static class Cloud {
    int x, y;

    public Cloud(int x, int y) {
      this.x = x;
      this.y = y;
    }

    /**
     * direction 방향으로 speed 만큼 이동
     * @param direction : 방향
     * @param speed : 거리
     */
    void move(int direction, int speed) {
      x = (x + dx[direction]*speed + (speed+1)*N) % N; // (speed+1)*N을 더하면 무조건 음수가 아님
      y = (y + dy[direction]*speed + (speed+1)*N) % N;
    }

    /**
     * 비가 내려 구름이 있는 칸의 바구니에 저장된 물 증가
     */
    void rain() {
      arr[x][y]++;
    }

    /**
     * 물 복사 버그 마법
     * 대각선 방향 칸에 물이 있는 바구니 수만큼 물 증가
     * 경계를 넘어가는 칸은 생각X
     */
    void waterCopyBug() {
      int[] crossX = {1,1,-1,-1};
      int[] crossY = {-1,1,-1,1};
      int waterCnt = 0;

      for(int i=0; i<crossX.length; i++) {
        int cx = x + crossX[i];
        int cy = y + crossY[i];
        // 범위 벗어나면 패스
        if(cx < 0 || cx >= N || cy < 0 || cy >= N) continue;
        // 물이 안담겨있으면 패스
        if(arr[cx][cy] == 0) continue;
        waterCnt++;
      }
      // 물 담겨있는 수만큼 물복사 버그!
      arr[x][y] += waterCnt;
    }

    /**
     * 현재 자리가 구름이 있던 자리임을 나타내기
     */
    void stamp() {
      arr[x][y] = -arr[x][y];
    }
  }
}