문제

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example 2:
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j] is 0 or 1.

관련있는 주제

Array, Matrix, Simulation

아이디어

살아있는 cell 에서는 주변이웃에 살아있는 셀이 2,3 개 일때만 유지되고 1개 혹은 4개 이상은 인구 감소, 인구 폭증으로 인해 죽게 된다.

죽어있는 cell 에서는 주변 이웃의 살아있는 셀이 3개 일때 재생산되어 살게 된다.

이는 주변 셀이 살아있는지 여부가 각 셀에게 매우 중요하니 중간에 셀의 데이터를 바꿔버리면 아직 읽지 않은 셀은 변경된 데이터를 읽게 된다.

그러니 문제에서 in-place 라는 조건이 안보이니 m x n 크기의 matrix 를 만들어두고 모든 셀을 brute-force 로 방문하여 그 셀의 좌표 j, i 를 읽은 뒤, 그 셀의 neighbors 중 살아있는 셀의 수를 읽고 j, i 셀이 다음 generation 때 살지 죽을지를 판단하여 새로 생성한 matrix 에 저장한 뒤

마지막에 board 의 각 값에 넣는 식의 코드를 생각했다.

/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function(board) {
    let obj = {
        x: 0,
        y: 0,
        isLive: false
    };
    let result = new Array(board.length).fill(null).map(() => new Array(board[0].length));

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            let cell = isLiveOrDead({
                ...obj,
                x: j,
                y: i,
                isLive: board[i][j]
            }, board);
            result[i][j] = cell.isLive;
        }
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            board[i][j] = result[i][j]
        }
    }
};

function isLiveOrDead (cell, board) {
    let count = numOfLive(cell.x, cell.y, board);
    switch (count) {
        case 0: 
        case 1: 
            if (cell.isLive) cell.isLive = 0;
            break;
        case 2:
            if (cell.isLive) cell.isLive = 1;
            break;
        case 3:
            cell.isLive = 1;
            break;
        default: cell.isLive = 0;
            break;
    } 

    return cell;
}

function numOfLive (x, y, board) {
    let count = 0;

    for (let i = y - 1; i <= y + 1 ; i++) {
        for (let j = x - 1; j <= x + 1; j++) {
            // m x n 범위 내에 있고 본인과 겹치지 않는 주변
            if (i >= 0 && j >= 0 && i < board.length && j < board[0].length && !( i === y && j === x ) && board[i][j] === 1 ) {
                count++;
            }
        }
    }

    return count;
}

이때 문제가 새로운 matrix 인 result 를 만들어줬는데 문제에서는 in-place 라는 조건이 없는데 제출답안 return 을 보니 board 를 in-place 로 수정하라는 부분이 보였다.

그래서 result 를 만들지 않고 직접 board 를 수정해야 하는 방법을 찾다가 2시간이 넘어서 다른 분들의 풀이를 보고 좋은 아이디어를 가져왔다.

결국 해당 셀이 살아있는지 여부는 truthy 인지만 if 조건문에서 확인한다.

그러나 원래 cell 이 live 였던 경우와 다음 상태에서도 live 인 경우가 구분되어야 하니 결과에 2를 곱한뒤 원래 값과 더하는 방식의 아이디어였다.

그러고 나서 결과에 적용할때는 1또는 3일때만 live 가 되고 결과를 나타낼 때 각 데이터를 2로 나눈 몫을 구해서 다음 상태가 3일때만 나타나도록 하는 것이었다.

말로 표현하려니 좀 어색한데 코드로 보자.

/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function(board) {
    let obj = {
        x: 0,
        y: 0,
        isLive: false
    };

    const m = board.length;
    const n = board[0].length;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] = isLiveOrDead({
                ...obj,
                x: j,
                y: i,
                isLive: board[i][j]
            }, board) * 2 + board[i][j];
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] = Math.floor(board[i][j] / 2);
        }
    }
};

function isLiveOrDead (cell, board) {
    let count = numOfLive(cell.x, cell.y, board);
    let result = 0;
    switch (count) {
        case 0: 
        case 1: 
            if (cell.isLive) result = 0;
            break;
        case 2:
            if (cell.isLive) result = 1;
            break;
        case 3:
            result = 1;
            break;
        default: result = 0;
            break;
    } 

    return result;
}

function numOfLive (x, y, board) {
    let count = 0;
    const m = board.length;
    const n = board[0].length;

    for (let i = y - 1; i <= y + 1 ; i++) {
        for (let j = x - 1; j <= x + 1; j++) {
            // m x n 범위 내에 있고 본인과 겹치지 않는 주변
            if (i >= 0 && 
                j >= 0 && 
                i < m && 
                j < n && 
                !( i === y && j === x ) && 
               (board[i][j] === 1 || board[i][j] === 3) ) {
                count++;
            }
        }
    }

    return count;
}

나는 다음 상태에서 각 셀이 살았는지 죽었는지 구하는 isLiveOrDead 라는 함수를 만들고 그 함수에서는 neighbors 의 live 수를 구해 문제에서 주어진 4가지 조건에 따라 살지 죽을지 여부를 반환한다.

이때 다음 상태에서도 사는 경우 데이터가 3이 되고 다음 상태에서 죽지만 현재는 살아있을 경우엔 데이터가 1이 되어 isLiveOrDead 의 조건문에 동일한 결과를 내도록 했다.

다만 최종적으로 board 에 값을 반영할 때는 2로 나눈 몫을 데이터에 나타나도록 하여 중간에 값이 in-place 로 바뀌지만 계산에는 영향이 없도록 하는 코드가 된다.