백준 17232 생명 게임 (JAVA)

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

17232번: 생명 게임

 

문제 설명

바둑판 안에서 계속 움직이는 생명에 위치를 알아내는 게임입니다. 이 때 각칸은 주위의 영향을 받습니다.

여기서 말한 주위는 색칠한 영역과 같이 현재 칸을 중심으로 둔 한 변의 길이가 (2K+1)인 정사각형 입니다. (단, 현재 칸 제외)

1. 생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다.
2. 고독 : 만약 현재 칸에 생명이 있고, 주위에 a개 미만의 생명이 있다면 현재 칸의 생명은 외로워서 죽는다.
3. 과밀 : 만약 현재 칸에 생명이 있고, 주위에 b개 초과의 생명이 있다면 현재 칸의 생명은 과밀로 죽는다.
4. 탄생 : 만약 현재 칸에 생명이 없고, 주위에 a개 초과 b개 이하의 생명이 있다면 다음 단계에서 현재 칸에 생명이 생긴다.

이렇게 존재한다고 할 때 만약 한번 움직이면 어떻게 될까? 지금 K는 1이다. 즉 3 * 3 정사각형이 주위입니다.

a는 2이고 b는 3이다.

첫 번째 자신의 구역을 검사하면 이렇게 변경됩니다. 이렇게 변경하기 위해서는 모든 칸을 조사해 봐야합니다.

 

문제에 대한 아이디어

생명을 움직이기 위해서는 모든 칸을 조사해봐야 합니다. 그래야 다음 어떤 행동을 할지 정할 수 있습니다.

하지만 시간제한은 2초입니다. 매 시간마다 모든 K*K를 조사하면. 시간 복잡도는 N*M*(K*K)*T 일 것이고 2초를 넘을 수가 있습니다.

해결책을 생각해본 결과 구역에 대한 정보를 미리 저장하고 있으면 K*K를 줄일 수 있다고 생각했습니다.

그래서 생각한 방법은 구간합입니다.

각 T마다 바둑판에 대한 구간합 정보 2차원 배열을 만듭니다. 그 후 구간합 2차원 배열을 가지고 구간에 대한 조건을 처리 해줍니다.

for(int i = 0; i < t; ++i) {
    // 매 T 마다 현재 바둑판에 대한 구간합 배열을 만듬.
    int tempPrefixSums[][] = makePrefixSum(boards);

    for(int y = 1; y <= n; ++y) {
        for (int x = 1; x <= m; ++x) {
            // 구간합 배열을 가지고 조건 조사
            checkSide(a, b, k, tempPrefixSums, y, x, n, m, boards);
        }
    }
}

구간합 배열 만들기

 

public static int[][] makePrefixSum(int[][] boards) {
    // 현재 바둑판 정보를 깊은 복사를 합니다.
    int[][] prefixSum = new int[boards.length][boards[0].length];
    for(int i = 0; i < boards.length; ++i) {
        prefixSum[i] = boards[i].clone();
    }

    // 현재 바둑판 정보를 가지고 2차원 구간합을 만듭니다.
    for(int i = 1; i < boards.length; ++i) {
       for(int j = 1; j < boards[i].length; ++j) {
           prefixSum[i][j] = prefixSum[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
       }
    }
   return prefixSum;
}

조건에 맞게 해결하기

public static void checkSide(int a, int b, int k, int[][] tempPrefixSums, int y, int x, int n, int m, int boards[][]) {
   int sy = y - k; int sx = x - k;
   int ey = y + k; int ex = x + k;
   if(sy <= 0) sy = 1; if(sx <= 0) sx = 1;
   if(ey > n) ey = n; if(ex > m) ex = m;
   int count = tempPrefixSums[ey][ex] - tempPrefixSums[sy-1][ex] - tempPrefixSums[ey][sx-1] + tempPrefixSums[sy-1][sx-1] ;
   if(boards[y][x] == 1) {
       count -= 1;
       if(a <= count && count <= b) {
            // 생존
            return;
       }
       else if (count < a) {
            // 고독
            boards[y][x] = 0;
       }
       else if (count > b) {
            // 과밀
           boards[y][x] = 0;
       }
   }
   else {
        if(a < count && count <= b) {
            // 탄생
            boards[y][x] = 1;
       }
   }
}