[LeetCode] 289. Game of Life

Problem

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.

---

Solution

class Solution {
    public void gameOfLife(int[][] board) {
        int[][] newBoard = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                makeNewBoard(board, newBoard, i, j);
        // board = newBoard; 안되네;;
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                board[i][j] = newBoard[i][j];
    }
    private void makeNewBoard(int[][] board, int[][] newBoard, int row, int col) {
        int liveNeighbors = 0;
        for (int i = row - 1; i < row + 2; i++)
            for (int j = col - 1; j < col + 2; j++) {
                if (i < 0 || board.length - 1 < i || j < 0 || board[0].length - 1 < j || i == row && j == col) continue;
                else if (board[i][j] == 1) liveNeighbors++;
            }
        if (board[row][col] == 0)
            newBoard[row][col] = liveNeighbors == 3 ? 1 : 0;
        else if (board[row][col] == 1)
            newBoard[row][col] = liveNeighbors == 2 || liveNeighbors == 3 ? 1 : 0;
    }
}

Explanation

• 배열 board의 요소들이 살아있는 이웃을 얼마나 많이 가지고 있는지 확인해야 한다. 그리고 모든 요소가 가진 개별적인 이웃의 수를 모두 체크할 때까지 배열 board의 요소에는 변화가 없어야 한다. 따라서 새로운 배열을 선언하여 배열 board의 이웃의 수에 따른 변화를 메모하도록 한다.
• 새로운 2차원 배열 newBoard를 선언하고, 배열 newBoard의 요소에 알맞은 값을 할당하기 위한 makeNewBoard()를 선언한다. makeNewBoard()를 호출할 때 필요한 인수로는 배열 board와 mewBoard 그리고 현재 참조하고 있는 배열 board의 인덱스이다.

  int[][] newBoard = new int[board.length][board[0].length];
  for (int i = 0; i < board.length; i++)
    for (int j = 0; j < board[0].length; j++)
        makeNewBoard(board, newBoard, i, j);
  

• 다음으로 makeNewBoard()의 선언부를 작성한다. 그리고 주변 이웃의 수를 구하고 배열 newBoard에 값을 할당하는 구현부를 작성한다. 이 때 인덱스 참조 범위 예외를 피하기 위해 참조할 수 없는 인덱스 또는 자기자신을 가리키는 인덱스는 continue 키워드로 건너뛰도록 한다.

  private void makeNewBoard(int[][] board, int[][] newBoard, int row, int col) {
    int liveNeighbors = 0;
    for (int i = row - 1; i < row + 2; i++)
        for (int j = col - 1; j < col + 2; j++) {
            if (i < 0 || board.length - 1 < i || j < 0 || board[0].length - 1 < j || i == row && j == col) continue;
            else if (board[i][j] == 1) liveNeighbors++;
        }
    if (board[row][col] == 0)
        newBoard[row][col] = liveNeighbors == 3 ? 1 : 0;
    else if (board[row][col] == 1)
        newBoard[row][col] = liveNeighbors == 2 || liveNeighbors == 3 ? 1 : 0;
  }
  

• 값이 할당된 배열 newBoard의 요소들을 그대로 배열 board에 할당해준다.

  for (int i = 0; i < board.length; i++)
    for (int j = 0; j < board[0].length; j++)
        board[i][j] = newBoard[i][j];