[Leetcode] 289. Game of Life - JS

https://leetcode.com/problems/game-of-life/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
- 초기값 cell에 live면 1, dead면 0으로 나타난 m x n 구조
- 각 cell은 8명의 이웃과 아래 4개의 규칙에 따라 상호작용한다.

조건 1. 이웃한 cell 중 live가 2개 미만일 때, 자기 자신이 live면 죽는다.
조건 2. 이웃한 cell 중 live가 2 ~ 3개일 때, 자기 자신이 live면 유지된다. 
조건 3. 이웃한 cell 중 live가 3개 초과이고, 자기 자신이 live면 죽는다.
조건 4. 이웃한 cell 중 정확히 3개 live가 존재하고 자기 자신이 dead면 산다.

- 탄생과 죽음은 동시에 일어나야한다.
즉, cell이 변경된 다음 상태값을 참조하여 다른 cell이 영향을 받으면 안된다.
- 현재 board 상태가 주어질 때, 위 조건을 적용하여 제자리에서 변경하라.

제한조건
--------------------
- m == board.length
- n == board[i].length
- 1 <= m, n <= 25
- board[i][j]는 0 또는 1이다.

 

2. 접근 방법

접근방법
--------------------
이웃한 cell을 판단한다. 이웃한 cell은 [i-1 ~ i+1], [j-1 ~ j+1]
현재 상태를 기반으로 룰에 맞도록 미래 상태로 바꿔야 하므로 단순히 live, dead 만으로 판단하기 어렵다.

그러므로 아래와 같이 현재와 미래의 상태값이 다른 경우를 추가한다.

0: 현재 dead, 미래 dead
1: 현재 live, 미래 live
2: 현재 live, 미래 dead
3: 현재 dead, 미래 live

이웃 cell을 확인하여 1번 or 2번이면 즉, 현재 살아있는 cell 갯수를 카운트 한다. (neighbors)
neighbors 조건에 따라 board[i][j]의 상태값을 변경한다.

마지막에 board를 순회하면서 2,3번인 요소를 조건에 맞게 0, 1로 바꿔준다.

 

 

3. 코드

var gameOfLife = function(board) {
    const rows = board.length;
    const cols = board[0].length;

    const directions = [
        [-1,-1], [-1, 0], [-1, 1],
        [0, -1],          [0, 1],
        [1, -1],  [1, 0], [1, 1]
    ]

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            let neighbors = 0;

            // 이전 상태에서 살아있는 이웃의 갯수
            for (let [dx, dy] of directions) {
                const newRow = i + dx;
                const newCol = j + dy;

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                    if (board[newRow][newCol] === 1 || board[newRow][newCol] === 2) {
                        neighbors++;
                    }
                }
            }

            // 조건 1과 조건 3
            if (board[i][j] === 1 && (neighbors < 2 || neighbors > 3)) {
                board[i][j] = 2
            } else if (board[i][j] === 0 && neighbors === 3) {
                board[i][j] = 3
            }
        }
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 2) {
                board[i][j] = 0
            } else if (board[i][j] === 3) {
                board[i][j] = 1
            }
        }
    }
};

 

 

 

4. 복잡도 분석

- 시간복잡도: O(n^2)

- 공간복잡도: O(1)

 

GPT에게 물어봐서 문제 풀이를 공부했다.

문제에서 주어진 0(dead), 1(live) 두 가지 상태값으로 풀기 어려우니 현재와 미래의 상태값이 다른 2(live -> dead), 3(dead -> live) 값도 추가하는 방법이 신박했다.