[C++/LeetCode] Game of Life

Daily LeetCoding Challenge for April, Day 12

 

문제

2차원 vector의 값을 규칙에 맞게 변경하기

 

아이디어

2차원 vector를 돌면서 이웃한 cell 중에서 몇개의 1이 있는지 확인한 후, 값을 정한다.

 

 

완성

submission: 6ms / 6.9MB

 

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int row = board.size();
        int col = board[0].size();
        
        vector<vector<int>> result(row, vector<int> (col, 0));
        
        for(int i = 0;i < row;i++)
        {
            for(int j = 0;j < col;j++)
            {
                int sum = 0;
                for(int n = i - 1;n <= i + 1;n++)
                {
                    for(int m = j - 1;m <= j + 1;m++)
                    {
                    	// 중앙 cell과 벡터의 범위를 벗어나는 cell은 제외
                        if ((n != i || m != j) && (n >= 0 && m >= 0 && n < row && m < col))
                        {
                            if (board[n][m] == 1)
                                sum++;
                        }
                    }
                }
                
                if (board[i][j] == 0)
                {
                    if (sum == 3)
                        result[i][j] = 1;
                    else
                        result[i][j] = 0;
                }
                else
                {
                    if (sum < 2)
                        result[i][j] = 0;
                    else if (2 <= sum && sum <= 3)
                        result[i][j] = 1;
                    else if (sum > 3)
                        result[i][j] = 0;
                }
            }
        }
        
        for(int i = 0;i < row;i++)
        {
            for(int j = 0;j < col;j++)
            {
                board[i][j] = result[i][j];
            }
        }
    }
};

 

처음에는 board 자체에 값을 넣어보려고 했는데, board 값을 바꾸면 다른 cell의 상태에 영향을 주기 때문에 새로 vector를 생성해서 복사할 수 밖에 없었다. 근데 다른 사람들 코드를 보니 비트 연산을 해서 space를 O(1)로 만든 사람이 있었다. 비트 연산을 좀 더 공부해야겠다.