[LeetCode]Game of Life

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 규칙에 따라서 생존하거나 소생하는 경우를 구하는 문제입니다.

 

처음 시도한 답안

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

        dx = [0,-1,0,1,1,1,-1,-1]
        dy = [1,0,-1,0,1,-1,1,-1]

        for i in range(r):
            for j in range(c):
                live_cnt = 0
                for idx in range(8):
                    x = i + dx[idx]
                    y = j + dy[idx]
                    if x < 0 or x >= r or y < 0 or y >= c:
                        continue
                    
                    if board[x][y] == 1 or board[x][y] == 'F':
                        live_cnt += 1

                if board[i][j] == 0:
                    if live_cnt == 3:
                        board[i][j] = 'T'

                elif board[i][j] == 1:
                    if live_cnt < 2 or live_cnt > 3:
                        board[i][j] = 'F'

        for i in range(r):
            for j in range(c):
                if board[i][j] == 'T':
                    board[i][j] = 1
                elif board[i][j] == 'F':
                    board[i][j] = 0

접근 방법

1. 특별한 알고리즘 없이 주어진 규칙을 따르면 되는 문제입니다.
2. dx, dy에는 본인의 위치를 제외한 주변 위치를 탐색하기 위한 용도로 사용했습니다. 
3. row와 col의 수만큼 이중 순회합니다.
   1. 주변을 탐색하기 위해 8번 순회합니다.
      1. 새로운 위치 x, y를 dx와 dy를 이용해 구합니다.
      2. 만약 위치가 board를 벗어났다면 넘어갑니다.
      3. 주변에 사람이 생존해있다면 live_cnt를 1 증가합니다. (F 처리도 살리는 경우는 현재는 누군가 살아있기 때문입니다)
   2. 순회 이후에 사람이 없던 지역일 때 주변에 3명이 살아있다면 사람을 살리기 위해 T라고 기록합니다.
   3. 순회 이후에 사람이 있던 지역일 때 주변에 2명보다 적거나 3명을 초과해 있다면 사람을 없애기 위해 F라고 기록합니다.
4. 이중 순회를 마친 이후에 T로 표시된 곳은 1처리 F로 표시된 곳은 0처리 합니다.

해당 문제에서 리스트를 한번에 업데이트를 하기 위해 T와 F라는 마킹 개념을 사용했습니다. 그래서 live_cnt를 체크할 때 F인 경우도 확인하는 것입니다.

T는 0->1이 되는 상황이고 F는 1->0이 되는 상황입니다. T, F가 기록이 되어있지 않은 곳은 현 상태를 유지하는 곳입니다.

 

이 문제는 크게 4가지의 경우의 수가 존재합니다.

- 0 -> 1로 살리는 경우, T로 마크처리 합니다.

- 1 -> 0로 죽이는 경우, F로 마크처리 합니다.

- 0 -> 0로 유지되는 경우, 그대로 유지합니다.

- 1 -> 1로 유지되는 경우, 그대로 유지합니다.