[240305] 알고리즘 리부트 24일차 - 백준 17232 자바

[Part1-Chapter05-Clip04]

- 백준 17232 생명게임

이전에 푼 구간합 구하기 5의 풀이 과정을 담으면 되는 문제였다. 동일한 문제였지만 *라는 문자로 변경되었다고 누적합을 생각해내지 못해서 강의를 보고 나서야 반영할 수 있었다..

누적합 배열을 별도로 만들지 않으면 원래 배열에서 변화를 주게되고 그럼 다음 원소를 탐색할 때 변경된 값을 참조하는 큰 문제가 있다. 또한 반복문을 순회하면서 변경사항을 반영하다보면 시간 복잡도가 커지기 때문에 변경되는 부분을 누적합을 먼저 구해주고 한번에 반영하는 것이 시간 초과하지 않는 방법이다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

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

        char[][] arr = new char[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String str = br.readLine();
            for (int j = 1; j <= m; j++) {
                arr[i][j] = str.charAt(j - 1);
            }
        }

        while (t-- > 0) {
            int[][] acc = getPrefixSum(arr);

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    int aroundLives = getAroundLives(i, j, acc, k);
                    if (arr[i][j] == '*') {
                        aroundLives--; // 현재 본인은 제외
                        if (aroundLives < a || aroundLives > b) {
                            arr[i][j] = '.'; // 사망
                        }
                    } else if (aroundLives > a && aroundLives <= b) {
                        arr[i][j] = '*';
                    }
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                bw.write(arr[i][j]);
            }
            bw.write("\n");
        }
        bw.flush();
    }

    private static int getAroundLives(int r, int c, int[][] acc, int k) {

        int startR = Math.max(r - k, 1);
        int startC = Math.max(c - k, 1);
        int endR = Math.min(r + k, acc.length - 1);
        int endC = Math.min(c + k, acc[0].length - 1);

        return acc[endR][endC] - acc[startR - 1][endC] - acc[endR][startC - 1] + acc[startR - 1][startC - 1];
    }

    private static int[][] getPrefixSum(char[][] arr) {

        int[][] acc = new int[arr.length][arr[0].length];

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + (arr[i][j] == '*' ? 1 : 0);
            }
        }

        return acc;
    }
}