[Leetcode] Game of Life (#289)

 

 

문제 

 

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):

1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population.
4. 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.

 

 

예제 

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]]

 

 

해설 코드 

class Solution(object):
    def gameOfLife(self, b):
        m,n = len(b),len(b[0])
        dirs = [(1,0),(-1,0),(0,1),(0,-1),(-1,1),(-1,-1),(1,-1),(1,1)]
        
        for i in range(m):
            for t in range(n):
                livecount = 0
                
                # 정해진 구역 내에 있는 1의 숫자를 센다. 
                for r,c in dirs:
                    nr,nc = i+r,t+c
                    if 0 <= nr < m and 0 <= nc < n and abs(b[nr][nc]) == 1:
                        livecount += 1
                
                # 수가 변할 때에만 새로운 수를 넣어준다. 
                if b[i][t] == 1:
                    if livecount < 2 or livecount > 3:
                        b[i][t] = -1
                else:
                    if livecount == 3:
                        b[i][t] = 2
        
        # 바뀌었던 수를 다시 0 혹은 1로 바꾸어준다. 
        for i in range(m):
            for t in range(n):
                if b[i][t] == -1:
                    b[i][t] = 0
                if b[i][t] == 2:
                    b[i][t] = 1
        print(b)

분석 > 이 코드의 기본적인 전개 과정은 우선 이웃하는 8개의 수 중에서 1의 개수를 세고 그에 따라 수가 변화한다면 1이 아닌 수 (왜냐하면 그 자리에서 수를 바꾼다면 찾고자 하는 1의 수가 달라질 수 있기 때문) 로 바꾸어 주고 후에 바뀐 수를 다시 0 혹은 1로 바꾸어줌으로써 배열을 반환하는 것이다. 여기서 이웃하는 8개의 수 중에서 1의 개수를 찾을 때는 정해진 구역 내, 즉 방향키를 이용해 움직였을 때 최소인 0 이상 최대인 m 과 n 미만의 구역 내에 포함되면서 ( n과 m이 포함되는 경우는 자기 자신도 셀 수 있기 때문) 절대값이 1인 경우의 수만 세어 lifecount 에 넣어주면 된다. 처음 이 문제를 접했을 때, 이웃하는 8개의 수를 어떻게 탐색할지 좀처럼 감을 잡을 수 없었는데 이번 문제를 통해 튜플을 이용해 방향키를 만들어 탐색할 수 있음을 배울 수 있었다. 

 

 

 

Game of Life - LeetCode