[LeetCode] 289. Game of Life

https://leetcode.com/problems/game-of-life/

Game of Life - LeetCode

Game of Life

 

 

The Game of Life 의 법칙에 따라 각 셀의 state 가 변한다.

- 해당 state 가 1이고, 이웃 (주변 8칸)의 state 의 합이 2보다 작을 경우, 해당 state 는 다음 세대에 0 이 된다.

- 해당 state 가 1이고, 이웃 (주변 8칸)의 state 의 합이 2나 3일 경우, 해당 state 는 다음 세대에도 1이다.

- 해당 state 가 1이고, 이웃 (주변 8칸)의 state 의 합이 3보다 클 경우, 해당 state 는 다음 세대에 0 이 된다.

- 해당 state 가 0이고, 이웃 (주변 8칸)의 state 의 합이 3일 경우, 해당 state 는 다음 세대에 1 이 된다.

 

즉 해당 state가 1이고 이웃이 2나3일 경우엔 유지, 아닐 경우엔 0

해당 state가 0이고 이웃이 3일 경우엔 1, 아닐 경우 유지가 된다.

 

가상의 board를 하나 더 만들어 한칸한칸 훑으며 주변 여덟칸을 조사하고, 가상의 board에 다음 세대 정보를 입력하면 간단하다.

하지만 여기에는 없지만 문제 추가 조건에 in-place로 풀어보라는 이야기가 있는데 이러면 조금 생각을 해야한다.

 

생각해낸 in-place 풀이법은 아래와 같다.

일반적으로 for문을 돌려 어떤 칸의 차례가 되었을 때, 방문 정보는 아래 표와 같다.

방문 O (1)	방문 O (2)	방문 O (3)
방문 O (4)	현재 칸	방문 X (5)
방문 X (6)	방문 X (7)	방문 X (8)

1,2,3,4 번 칸은 방문되었으니 고려하지 말고 5,6,7,8 칸만 영향을 주며 현재 칸을 바꾸어야 한다.

총 이웃칸은 8칸이고, 각 칸은 0또는 1의 상태를 가진다.

여기서 약간 꾀를 쓰면 내 상태는 그대로 두고 이웃의 칸은 10을 곱해 내 칸에 더해주면 된다.

즉, 현재 칸 방문 직전 상태는 10*(1번칸 + 2번칸 + 3번칸 + 4번칸) + 현재 칸 의 상태가 되어있을 것이고,

현재 칸 방문시에 10*(5번칸 + 6번칸 + 7번칸 + 8번칸) 을 현재 칸에 더해 주고,

5,6,7,8번칸에 10*현재칸을 더해주면 된다.

그러면 별도의 board를 만들 필요 없이, 현재칸과 이웃칸의 값이 구별이 되고, 현재칸이 변경되어도 이웃칸에는 영향이 없어진다.

여기서 주의할 것이 있는데 칸의 값을 그대로 10을 곱해 더하면 절대 안되고, 1의 자리만 더해줘야한다. 

%10을 통해 1의자리만 곱해 더해주자.

 

이제 현재칸의 다음 세대값을 구해보자.

 

해당 state가 1이고 이웃이 2나3일 경우엔 유지, 아닐 경우엔 0 => 현재칸 = 21 또는 31

해당 state가 0이고 이웃이 3일 경우엔 1, 아닐 경우 유지가 된다. => 현재칸 = 30

 

즉, 현재칸 방문을 하고 이웃칸 값을 더했을 때, 현재칸의 값이 21,30,31 이면 1로, 아니라면 0으로 업데이트를 해주면 된다.

범위만 조심하여 코드를 짜주자.

 

전체 풀이 코드

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int x[4] = {1, -1, 0, 1}, y[4] = {0, 1, 1, 1};
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                int sum = board[i][j];
                for (int k=0; k<4; k++) if (i+y[k]<board.size() && j+x[k]<board[0].size() && j+x[k]>=0) {
                        sum += 10 * (board[i+y[k]][j+x[k]]%10);
                        board[i+y[k]][j+x[k]] += 10*(board[i][j]%10);
                }
                if (sum==30 || sum==21 || sum == 31) board[i][j] = 1;
                else board[i][j] = 0;
            }
        }
    }
};