leetcode medium : Game of Life

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

Game of Life - LeetCode

 

Game of Life

풀기 전

상태 관리를 하면 쉽게 풀 수 있을 것 같다.

0, 1 외에 두 개의 상태를 더 만드는 것이다.

현재 살아있지만 다음 세대에 죽을 상태

현재 죽었지만 다음 세대에 살아날 상태

그리고 마지막에 두 상태를 각각 0, 1로 치환하면 된다.

코드 설명

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        def countLiveNeighbors(r, c):
            dx = [-1, -1, -1, 0, 0, 1, 1, 1]
            dy = [-1, 0, 1, 1, -1, 1, -1, 0]

            count = 0
            for i in range(8):
                x = r + dx[i]
                y = c + dy[i]
                if x >= 0 and x < len(board) and y >= 0 and y < len(board[0]):
                    count += 1 if board[x][y] in (1, 3) else 0
            return count

        """
        0 - dead
        1 - live
        2 - dead and will replace to live
        3 - live and will replace to dead
        """
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                count = countLiveNeighbors(i, j)
                
                if board[i][j] == 1 and (count < 2 or count > 3):
                    board[i][j] = 3
                elif board[i][j] == 0 and count == 3:
                    board[i][j] = 2
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 3:
                    board[i][j] = 0
                elif board[i][j] == 2:
                    board[i][j] = 1

• countLiveNeighbors 함수는 특정 셀 기준으로 주변의 살아있는 셀을 세어주는 함수다.
• 첫 번째 for문은 보드의 모든 셀에 대해 규칙에 따라 셀의 상태값을 수정한다.
• 두 번째 for문은 임시로 만들어두었던 상태를 유효한 상태(0,1)로 치환한다.

복잡도 분석

보드가 M x N일때 시간복잡도는 O(MN)이고 공간복잡도는 O(1)이다.