[JAVA] LeetCode - Game of Life - 289

문제내용

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

Game of Life - LeetCode

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.

 

Example 1:

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

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j] is 0 or 1.

 

Follow up:

• Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
• In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

---

문제 접근 방법

문제 내용을 간단하게 설명하자면 2차원 배열을 주고 각 요소마다 상하,좌우,대각선과 이웃하는 정점이 0인지 1인지를 구분해 조건에 맞게 2차원 배열을 업데이트 해주면 되는 문제이다. 조건은 아래와 같다.

 

조건

 1. 살아있는 이웃이 2개 미만인 살아있는 세포는 마치 인구 부족으로 인한 것처럼 죽습니다.
 2. 2~3개의 살아있는 이웃이 있는 살아있는 세포는 다음 세대까지 살아갑니다.
 3. 3개 이상의 살아있는 이웃이 있는 살아있는 세포는 마치 인구 과잉으로 인해 죽습니다.
 4. 정확히 세 개의 살아있는 이웃이 있는 죽은 세포는 마치 번식에 의한 것처럼 살아있는 세포가 됩니다.

 

FollowUp

 1. 2차원배열을 한번에 업데이트 해야한다(동시에)

 2. 세포가 2차원배열의 경계값에서 경계값 밖으로 나가려하며 어케 처리할래?

 

우선 기본적인 알고리즘은 BFS이다. 그리고 위와 같은 조건을 가지고 board 배열을 수정하기 위해선 각 요소마다 이웃하는 1의 개수를 찾고 1의 개수에 따라 조건에 맞게 상태를 나타내주면 된다. 이때 동시에 업데이트 돼야하기 때문에 각 요소의 상태값을 저장해놓을 별도의 메모리 공간만 만들어주면 쉽게 풀수 있는 문제다.

 

다음 코드를 보고 생각해보자.

---

풀이

import java.util.ArrayList;
/*
 * 1. 살아있는 이웃이 2개 미만인 살아있는 세포는 마치 인구 부족으로 인한 것처럼 죽습니다.
 * 2. 2~3개의 살아있는 이웃이 있는 살아있는 세포는 다음 세대까지 살아갑니다.
 * 3. 3개 이상의 살아있는 이웃이 있는 살아있는 세포는 마치 인구 과잉으로 인해 죽습니다.
 * 4. 정확히 세 개의 살아있는 이웃이 있는 죽은 세포는 마치 번식에 의한 것처럼 살아있는 세포가 됩니다.
 * 
 * followUp
 * 1. 2차원배열을 한번에 업데이트 해야한다(동시에)
 * 2. 세포가 2차원배열의 경계값에서 경계값 밖으로 나가려하며 어케 처리할래?
 */
public class A0289_GameOfLife_Answer {
	public static void main(String[] args) {
		int[][] board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
		gameOfLife(board);
	}
	
	public static void gameOfLife(int[][] board) {
		ArrayList<GameOfLife289> res = new ArrayList<GameOfLife289>();//요소 상태 저장해놓을 list
		int rows = board.length;//행
		int col = board[0].length;//열
		
		//요소 하나씩 전부 검사
		for(int i=0; i<rows; i++) {
			for(int j=0; j<col; j++) {
				res.add(bfs(i,j,board));
			}
		}
		
		//res에 요소의 상태값을 가지고 board 동시에 업데이트
		//followUp 2번
		for(int i=0; i<res.size(); i++) {
			int x = res.get(i).x;
			int y = res.get(i).y;
			int state = res.get(i).state;
			
			board[x][y] = state;
		}
    }
	
	public static GameOfLife289 bfs(int v1, int v2, int[][] board) {
		GameOfLife289 game = null;
		int[] dx = {-1,1,0,0,-1,-1,1,1};//상하좌우대각
		int[] dy = {0,0,-1,1,-1,1,-1,1};//상하좌우대각
		int rows = board.length;//행
		int col = board[0].length;//열
		int aliveCnt = 0;//살아있는 세포 수
		
		//모든방향 검사
		for(int i=0; i<8; i++) {
			int nx = v1 + dx[i];
			int ny = v2 + dy[i];
			
			//경계값 넘어가면 continue(followUp 1번)
			if(nx<0 || ny<0 || nx>=rows || ny>=col) continue;
			
			//다음값이 살아있는 세포면 aliveCnt 증가.
			if(board[nx][ny]==1) { aliveCnt++; }
		}
		
		if(aliveCnt<2) game = new GameOfLife289(v1, v2, 0);//1번조건
		else if(aliveCnt>3) game = new GameOfLife289(v1, v2, 0);//2번조건
		else if(aliveCnt>=2 && aliveCnt<=3) {//3번조건
			if(board[v1][v2]==0) game = new GameOfLife289(v1,v2,0);
			else game = new GameOfLife289(v1,v2,1);
		}
		if(aliveCnt==3) game = new GameOfLife289(v1, v2, 1);//4번조건
		
		return game;
	}
}

class GameOfLife289{//상태값 알려줄 객체
	int x;
	int y;
	int state;
	public GameOfLife289() {}
	public GameOfLife289(int x, int y, int state) {
		this.x = x;
		this.y = y;
		this.state = state;
	}
}

---

마치며

최근에 백준이랑 프로그래머스 말고 LeetCode를 풀고 있다. 이유는 LeetCode의 토론게시판에 좋은 내용이 많다고 생각이 들었기 때문... 아무튼 앞으로는 LeetCode를 주로 포스팅할 예정이다.