[Leetcode] 289. Game of Life

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

---

m x n 2차원 배열이 있다. 배열은 1(live) 혹은 0(dead) 로 채워져 있다.

배열의 다음 상태는 각 셀의 8개의 이웃(수직, 수평, 대각선) 의 생사와 관련이 있다.

살아있는 상태의 셀의 살아있는 이웃 수가 2, 3개라면 다음에도 살아있을 수 있다. 하지만 이웃수가 너무적거나(0, 1) 너무 많으면(3초과) 인구과다로 죽게된다.

죽은 상태의 셀의 살아있는 이웃 수가 3개라면 번식한것처럼 되살아난다.

초기 생사 정보를 담은 배열이 입력으로 주어질 때 다음 상태를 반환하라.

---

m x n 배열을 하나 만들어서 모든 셀을 탐색하며 각 셀의 살아있는 이웃들의 수를 저장한다.

다시한번 입력 배열을 탐색하며 만일 살아있는 셀이면 이웃들의 수가 2, 3개면 1. 아닌 경우 0으로 갱신한다.

죽어있는 셀인 경우 이웃들의 수가 3이면 1. 아니면 0으로 갱신한다.

 

공간/시간복잡도는 O(NM).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/289.%20Game%20of%20Life.cpp