[JAVA][백준 17232] 생명게임

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

---

풀이 과정

이 문제는 엄청 복잡하긴하지만 푸는 방법 자체는 간단하다.

1. 시간이 1씩 지날때마다 생명배열을 누적합한 값을 기록하고

다시 배열을 쭉 보면서 해당 칸의 주변을 봤을때(2차원 배열의 누적합에서 구간에 따른 합을 구하는 방법을 사용해서 한번의 연산으로 구할 수 있다.)

다음 상태를 생존, 고독, 과밀, 탄생 4개중 어떤 상태가 될지 판단하여 변화를 주면 된다.

 

누적합을 매 시간마다 갱신한다는게 비효율적으로 보여서

이 방법이 맞나 싶은 생각이 들긴했는데 딱히 떠오르는 다른 방법이 없어서

그냥 그대로 구현을 했는데 통과한 문제.

 

구현에 중점이 되는 문제라서 좀 까다롭긴했다.

 

입력값을 받을때부터 처음엔 char 형태 그대로 저장을 할려고 했는데

매 시간마다 누적합을 구해놔야하는 부분때문에

계속 '*'인지 '.'인지 확인하는 것보단 1와 0으로 표현하고 계산하는게 낫겠다 싶어서 int[][]로 바꿔야하는 것도 어렵진 않지만 조금 귀찮은 부분이었고,

누적합 구하기 편하게 배열 크기를 (N + 1)*(M + 1)로 설정하는 것,

매번 누적합을 구해야하다보니 누적합 구하는 매소드를 따로 빼야 더 효율적인 것,

매번 주변 합을 구하는 것 등등...

문제 풀이 자체는 쉽지만 구현하는게 술술 되는 문제는 아니었다.

 

---

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int[][] sum, field;
    private static int N, M, T, K, A, B;
    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());   // 세로길이
        M = Integer.parseInt(st.nextToken());   // 가로길이
        T = Integer.parseInt(st.nextToken());   // 관찰 시간
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());   // 주위의 기준
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        // 입력
        field = new int[N + 1][M + 1];
        sum = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                field[i][j] = s.charAt(j - 1) == '*' ? 1 : 0;
            }
        }

        while (T-- > 0) {
            // 누적합 배열 구하기
            getInitSum();

            // 누적합 배열 결과에 따른 생명 상태 변경
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    int aroundSum = getAroundSum(i, j);

                    // 주변 생명의 개수에 따른 다음 상태 판단
                    // 현재 자리에 생명이 있을 때
                    if (field[i][j] == 1) {
                        aroundSum--;

                        // 생명 죽음 : a 개 미만, b 초과
                        if (aroundSum < A || aroundSum > B) {
                            field[i][j] = 0;
                        }
                    } else {
                        if (aroundSum > A && aroundSum <= B) {
                            field[i][j] = 1;
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (field[i][j] == 1) {
                    sb.append("*");
                } else {
                    sb.append(".");
                }
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static void getInitSum() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + field[i][j];
            }
        }
    }

    private static int getAroundSum(int r, int c) {
        int r1 = Math.max(1, r - K);
        int c1 = Math.max(1, c - K);
        int r2 = Math.min(N, r + K);
        int c2 = Math.min(M, c + K);

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

---

 

친구들과 스터디하면서 같이 푼 문제인데 친구들이 효율성 1등이라고 해서 봤더니
오잉...!!
1등했다 ^.^
그런데 같은 코드로 여러번 돌렸는데 계속 시간이 172~160 정도 왔다갔다 하는 걸 보면 요청을 언제하냐에 따라서 다른 것 같기도?
같은 코드도 시간이 계속 바뀌어서 저게 효율적인지 아닌지는 모르겠지만 일단 기분 좋으니깐 기록!

해당 문제 말고도 1등한 코드가 종종 몇개 있는데 누군가 내 풀이 코드를 훔쳐볼 때마다 뿌듯하다 ^.^