문제 설명

NxM 격자에서 생명(*)과 빈칸(.)이 존재한다.
각 칸은 주변의 영향을 받아 다음 상태로 변한다.

주변은 다음과 같이 정의된다.

현재 칸을 중심으로 (2K+1) × (2K+1) 영역
단, 자기 자신 제외

---

규칙

각 칸은 주변 생명 개수에 따라 상태가 변한다.

현재 칸에 생명이 있는 경우

조건	결과
a ≤ 주변 ≤ b	생존
주변 < a	고독 → 죽음
주변 > b	과밀 → 죽음

---

현재 칸이 빈칸인 경우

조건	결과
a < 주변 ≤ b	탄생
그 외	유지

---

입력

첫째 줄

N M T

둘째 줄

K a b

다음 N줄

초기 상태

---

출력

T번 시뮬레이션 후 최종 상태 출력

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

각 칸마다 주변 생명 개수를 빠르게 계산

---

왜 중요한가

단순 구현하면

각 칸마다 (2K+1)^2 탐색

시간복잡도

O(N × M × K² × T)

최악의 경우 매우 느려진다.

---

해결 방법

2차원 누적합 (Prefix Sum)

을 사용한다.

---

강의 코드

코드

import java.util.Scanner;

class Main
{
    static int[][] getPrefixSum(char[][] map) {

        int N = map.length - 1;
        int M = map[0].length - 1;

        int[][] acc = new int[N + 1][M + 1];

        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) {

                int alive = (map[i][j] == '*' ? 1 : 0);

                acc[i][j] = acc[i - 1][j]
                          + acc[i][j - 1]
                          - acc[i - 1][j - 1]
                          + alive;
            }

        return acc;
    }

    static int getRangeSum(int[][] acc, int r, int c, int K) {

        int r1 = Math.max(r - K, 1);
        int c1 = Math.max(c - K, 1);

        int r2 = Math.min(r + K, acc.length - 1);
        int c2 = Math.min(c + K, acc[0].length - 1);

        return acc[r2][c2]
             - acc[r1 - 1][c2]
             - acc[r2][c1 - 1]
             + acc[r1 - 1][c1 - 1];
    }

    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();

        int K = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();

        char[][] map = new char[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            String rowMap = sc.next();
            for (int j = 1; j <= M; j++)
                map[i][j] = rowMap.charAt(j - 1);
        }

        while (T-- > 0) {

            int[][] acc = getPrefixSum(map);

            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= M; j++) {

                    int nearAlive = getRangeSum(acc, i, j, K);

                    if (map[i][j] == '*') {

                        nearAlive--;

                        if (nearAlive < A || B < nearAlive)
                            map[i][j] = '.';
                    }

                    else if (A < nearAlive && nearAlive <= B)
                        map[i][j] = '*';
                }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++)
                System.out.print(map[i][j]);
            System.out.println();
        }
    }
}

---

내 코드 vs 강의 코드 비교

1. 풀이 방식

내 코드

없음

---

강의 코드

2차원 누적합 기반 시뮬레이션

---

2. 핵심 접근 방식

강의 코드는 다음 구조를 사용한다.

1. 누적합 생성
2. 범위 합 계산
3. 상태 업데이트

---

3. 핵심 함수 분리

누적합 생성

getPrefixSum()

→ 전체 생명 수를 빠르게 계산

---

범위 합 계산

getRangeSum()

→ K 범위 내 생명 수 계산

---

4. 중요한 차이

이 문제는 단순 구현이 아니라

속도 최적화 문제

이다.

---

단순 구현 vs 강의 코드

방식	특징
단순 구현	주변을 매번 직접 탐색
강의 코드	누적합으로 O(1) 계산

---

핵심 개념

1. 2차원 누적합

acc[i][j] = 위 + 왼쪽 - 겹친 부분 + 현재값

---

2. 범위 합 공식

사각형 영역 = 전체 - 위 - 왼쪽 + 겹친 부분

---

3. 시뮬레이션 문제

T번 반복

→ 매번 빠르게 계산해야 함

---

시간 복잡도

강의 코드

• 누적합 생성: O(N × M)
• 상태 업데이트: O(N × M)

전체

O(T × N × M)

최대

300 × 100 × 100 = 3,000,000

→ 충분히 가능

---

단순 구현 (비교)

O(T × N × M × K²)

→ 매우 느림

---

정리

이 문제는 단순한 생명 게임 문제가 아니라
2차원 누적합을 활용한 최적화 문제였다.

핵심은 다음이다.

범위 내 합을 빠르게 구하는 것

강의 코드는

누적합 + 범위 합 공식

을 사용하여 문제를 해결했다.

이 문제를 통해 배울 수 있는 점은 다음과 같다.

1. 2차원 누적합 활용
2. 범위 합 최적화
3. 시뮬레이션 + 최적화 결합 문제

즉,

시뮬레이션 문제라도
속도 최적화가 핵심일 수 있다

는 것을 보여주는 문제이다.