JAVA 백준 17232 생명 게임 (누적합, DP)

 

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

 

---

문제

1. 첫째 줄에 바둑판의 세로 길이 N, 가로 길이 M, 관찰하는 시간 T ( 1 <= N, M <= 100, 1 <= T <= 300 ) 이 입력된다.
2. 둘째 줄에 주위의 기준이 되는 정수 K, 각 칸의 다음 상황을 결정하는 정수 a, b ( 0 <= a, b <= ( 2 * K + 1 ) ^ 2 ) 이 입력된다.
3. 셋째 줄부터 N개의 줄에 걸쳐 각 줄에 M개씩 바둑판의 처음 상태가 주어진다. 생명이 있는 칸은 ' * ', 빈칸은 ' . ' 로 입력된다.
4. K를 이용하는 주위라는 것은 현재 칸을 중심으로 둔 한 변의 길이가 ( 2 * K + 1 ) 인 정사각형에서 현재 칸을 제외한 영역을 말한다.
5. 주위에 몇 개의 생명이 존재하는지에 따라 다음 명령을 수행하며, 생명은 바둑판을 벗어난 영역에서 생존할 수 없다.
   1. 생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다.
   2. 고독 : 만약 현재 칸에 생명이 있고, 주위에 a개 미만의 생명이 있다면 현재 칸의 생명은 외로워서 죽는다.
   3. 과밀 : 만약 현재 칸에 생명이 있고, 주위에 b개 초과의 생명이 있다면 현재 칸의 생명은 과밀로 죽는다.
   4. 탄생 : 만약 현재 칸에 생명이 없고, 주위에 a개 초과 b개 이하의 생명이 있다면 다음 단계에서 현재 칸에 생명이 생긴다.
6. T시간 뒤의 생명을 관찰하여 출력한다.

---

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        String[][] board = new String[N + 1][M + 1];

        st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            String[] temp = br.readLine().split("");
            for (int j = 1; j <= M; j++) {
                board[i][j] = temp[j - 1];
            }
        }

        for (int i = 0; i < T; i++) {
            int[][] sum = new int[N + 1][M + 1]; // 배열의 깊은 복사

            for (int y = 1; y <= N; y++) { // 복사한 배열의 구간합
                for (int x = 1; x <= M; x++) {
                    sum[y][x] = sum[y - 1][x] + sum[y][x - 1] - sum[y - 1][x - 1] + (Objects.equals(board[y][x], "*") ? 1 : 0);
                }
            }

            for (int y = 1; y <= N; y++) { // 현 단계의 결과
                for (int x = 1; x <= M; x++) {
                    int r1 = Math.max(y - K, 1);
                    int c1 = Math.max(x - K, 1);
                    int r2 = Math.min(y + K, N);
                    int c2 = Math.min(x + K, M);

                    int num = sum[r2][c2] - sum[r1 - 1][c2] - sum[r2][c1 - 1] + sum[r1 - 1][c1 - 1];

                    if (Objects.equals(board[y][x], "*")) {
                        num--; // 현재 칸의 수를 뺌
                        if (num < a || b < num) { // 고독, 과밀
                            board[y][x] = ".";
                        }
                    } else if (a < num && num <= b) { //탄생
                        board[y][x] = "*";
                    }
                }
            }
        }

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

 

 

어떻게 풀어야 될지 감은 금방 잡히나 금방 풀기는 힘들었다.

어떻게 합을 구하여 어떻게 값을 구해야 될지를 정하는 것이 관건인 문제인 듯 하다.

 

주위에 있는 생명의 수와 그 생명의 수를 구할 때 사용할 배열을 만드는 두 가지만 잘 만든다면 풀리는 문제인 것 같으나

나는 어려워서 혼자 풀지는 못했다.

배열까진 구했는데 주위에 있는 생명의 수를 어떻게 구해야 될 지 모르겠어서 도움을 조금 구했다.