[LeetCode] Game of Life

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

Game of Life - LeetCode

주위 살아있는 세포들의 개수를 세서 살아갈지 죽을지를 결정하는 문제다.

결론은 주위에 세포가 몇 개 살아있는지를 세면 된다.

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
        temp_board = [[0] * n for _ in range(m)]
        
        def OOB(x, y):
            return x < 0 or x >=m or y < 0 or y >= n
        
        def can_live(x, y):
            moves = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (-1, 1), (1, -1))
            live_cell = 0
            for move in moves:
                dx, dy = move
                nx, ny = x + dx, y + dy
                if not OOB(nx, ny) and board[nx][ny] == 1:
                    live_cell += 1
            if board[x][y] == 1:
                return True if live_cell in (2, 3) else False
            if board[x][y] == 0:
                return True if live_cell == 3 else False
            
        for i in range(m):
            for j in range(n):
                temp_board[i][j] = 1 if can_live(i, j) else 0
        
        for i in range(m):
            for j in range(n):
                board[i][j] = temp_board[i][j]

리스트보다 튜플이 빠른 것을 알고 난 이후에는 저런 moves 도 튜플로 생성하기로 했다. -- 약간이라도 빨랐으면 ㅎㅎ

 

이제 문제를 어느 정도 푸니깐 이런 느낌의 문제는 나름 고정된 풀이가 생기는 것 같다.

 

+공간 복잡도를 O(1)로 풀이할 수도 있다. board의 값을 적절하게 변경하면 된다.

예를 들어 기존에 1이 였는데 계산 후 살게 되면 board [x][y] = -1로 변경

기존에 0이 였는데 살게 되면 2 이런 식으로 하고 식만 조금 바꾸면 된다.