Conway's Game of Life 는 영국의 수학자 콘웨이가 고안한 게임으로 정사각형 그리드 공간을 기준으로 세포 (셀) 의 생성과 죽음을 통한 게임이다. 모든 칸은 세포 (셀) 이 있거나 없거나 두 가지 경우의 상태로 존재하고, 시간 (time-step) 이 경과함에 따라 그리드의 한 칸은 세포가 생길 수도, 사라질수도, 유지될 수도 있다.
다음 세대로 넘어가는 것을 하나의 시간이 경과하는 것이라고 하는데, 이 때, 세포 (셀) 의 생존과 죽음이 결정된다.
결정 기준은 다음과 같다. 하나의 칸을 볼 때, 그 칸에 인접한 8 개의 칸을 기준으로 해서 원래 세포가 살아있던 칸이면 인접한 셀의 수가 2 개 또는 3 개인 경우, 세포는 그대로 생존하고 그 외의 경우 (0, 1, 4, 5, 6, 7, 8 개) 에는 세포가 죽게 된다.
반대로 원래 세포가 없던 칸이면 인접한 셀의 수가 3 개인 경우에만 세포가 생겨난다. 그 외의 경우 (0, 1, 2, 4, 5, 6, 7, 8 개) 인 경우에는 세포가 없던 상태가 그대로 유지된다.
그렇다면 주어진 초기 상태를 기준으로 완전히 소멸하는데 걸리는 시간을 계산해보자.
주어진 그리드 공간의 크기는 무한하다고 가정한다. (진행하면서 벽에 막히거나 원통형처럼 생겨서 한 쪽 방향으로 계속 가면 다시 원래 위치로 돌아오는 경우는 없다고 하자.)
입력 3 4 1 0 0 1 1 1 1 1 1 0 0 1 출력 5 입출력 예시 1 보충설명 주어진 초기 상태는 다음과 같이 진행하면서 5 세대 이후에 사라진다. 초기 상태 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 1 세대 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 2 세대 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 3 세대 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 4 세대 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 5 세대 (완전 소멸) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 입력 2 2 1 1 1 1 출력 -1 입출력 예시 2 보충설명 주어진 초기 상태는 변화가 없이 영원히 지속가능한 상태이다.
출처: KangJ