리트코드 - 289. Game of Life

리트코드 - 289. Game of Life

출처 - https://leetcode.com/problems/game-of-life/

 

문제 설명

위키피디아 기사에 따르면 "The Game of Life", 또는 간단히 "Life"로 불리는 이 셀룰러 오토마톤은 1970년에 영국의 수학자 존 호튼 콘웨이가 고안했습니다.

게임판은 m x n 크기의 격자로 구성되어 있으며, 각 셀은 초기 상태인 살아있음(1로 표현됨)과 죽음(0으로 표현됨) 중 하나를 가집니다. 각 셀은 다음과 같은 네 가지 규칙을 사용하여 그것의 8개의 이웃 셀(수평, 수직, 대각선)과 상호작용합니다(위키피디아 기사에서 발췌):

1. 살아있는 셀이 두 개 미만의 살아있는 이웃을 가지고 있다면, 과소인구로 인해 죽습니다.
2. 살아있는 셀이 두 개 또는 세 개의 살아있는 이웃을 가지고 있다면, 다음 세대로 생존합니다.
3. 살아있는 셀이 세 개 이상의 살아있는 이웃을 가지고 있다면, 과밀로 인해 죽습니다.
4. 죽은 셀이 정확히 세 개의 살아있는 이웃을 가지고 있다면, 마치 번식에 의해 살아나는 것처럼 살아납니다.

다음 상태는 위의 규칙들을 현재 상태의 모든 셀에 동시에 적용함으로써 생성되며, 이때 출생과 죽음이 동시에 발생합니다. 주어진 m x n 격자판의 현재 상태에서, 다음 상태를 반환합니다.

 

풀이코드

class Solution {
    int r;
    int l;
    
    public void gameOfLife(int[][] board) {
        r = board.length;
        l = board[0].length;
        int[][] snapshot = new int[r][l];
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < l; j++) {
                int cur = board[i][j];
                snapshot[i][j] = dfs(board, i, j);
            }
        }
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < l; j++) {
                board[i][j] = snapshot[i][j];
            }
        }
    }
    
    public int dfs(int[][] board, int x, int y) {
        int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
        int[] dy = {0, 1, -1, 1, -1, 0, 1, -1};
        int count = 0;
        
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (canGo(board, nx, ny)) {
                count++;
            }
        }

        if (count == 2) {
            return board[x][y];
        }
        
        if (count == 3) {
            return 1;
        }

        return 0;
    }
    
    public boolean canGo(int[][] board, int nx, int ny) {
        return 0 <= nx && nx < r && 0 <= ny && ny < l && board[nx][ny] == 1;
    }
}

코드설명

2차원 배열을 탐색하여 값을 변경하는 문제로 조건을 요약하면 다음과 같다.

 

1. 주변셀이 2개 미만 또는 3개 초과 -> 현재 셀 0

2. 주변셀이 2개라면 -> 현재 셀 값 유지

3. 주변셀이 3개라면 -> 현재셀이 뭐든 상관없이 1

 

조건은 일단 이렇게 되고, 2차원 배열을 직접 수정하기가 까다로우므로 snapshot이라는 빈 배열을 복사했다.

그리고 값을 계산해서 이 값에 따라서 shapshot에 저장했다가, 다시 원래 배열인 board에 복사하면 된다.

 

탐색은 현재 기준 주변값을 탐색하므로 dfs가 적절해보여 택했다.

위/아래/왼쪽/오른쪽 탐색하는 것을 변형해서 8군데로 이동하도록 코드를 변형했다.

 

새로운 좌표가 이동가능한지 canGo() 메소드로 확인하여, 이동이 가능하면 count를 +1 더하게끔 했다.

 

이렇게 count를 더하게 된 다음 count가 2라면 board의 원래값을 리턴하면 되고, count가 3이라면 무조건 1을 리턴하면 된다.

if문에서 걸리지 않았다면 count는 2미만 3초과가 될 것이기 때문에 0을 리턴하게 했다.

 

최종적으로 snapshot을 완성한 다음, 이 값을 다시 board에 복사하면 문제가 해결된다.

 

이 코드를 In-Memory로 개선한 코드는 아래에 있다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

개선 코드

class Solution {
    int r;
    int l;
    
    public void gameOfLife(int[][] board) {
        r = board.length;
        l = board[0].length;
        int[][] snapshot = new int[r][l];
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < l; j++) {
                int cur = board[i][j];
                int neighbors = dfs(board, i, j);
                
                if (board[i][j] == 1 && (neighbors < 2 || neighbors > 3)) {
                    board[i][j] = 2;
                }
                
                if (board[i][j] == 0 && neighbors == 3) {
                    board[i][j] = 3;
                }
            }
        }
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < l; j++) {
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                    continue;
                }
                if (board[i][j] == 3) {
                    board[i][j] = 1;
                    continue;
                }
            }
        }
    }
    
    public int dfs(int[][] board, int x, int y) {
        int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
        int[] dy = {0, 1, -1, 1, -1, 0, 1, -1};
        int count = 0;
        
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (canGo(board, nx, ny)) {
                count++;
            }
        }
        return count;
    }
    
    public boolean canGo(int[][] board, int nx, int ny) {
        return 0 <= nx && nx < r && 0 <= ny && ny < l && (board[nx][ny] == 1 || board[nx][ny] == 2);
    }
}

앞에서 풀었던 문제에서도 그렇고 아래 심화과제(?)를 보면 In-memory안에 풀 수 있는지 묻고 있다.

현재 배열을 변경하면서 반복문을 순회할 때 문제가 발생하면 안된다.

 

이를 위해서 snapshot 배열을 없애고, count만 리턴하는 neighbors 변수만 하나 추가했다.

 

조건을 조금 더 개선해보자.

 

1) 현재 값이 1이면서 이웃 값이 2미만 3초과일 때만 0으로 변경되는 값이 된다.

2) 현재 값이 0이면서 이웃값이 3일 때만 1로 변경되는 값이 된다.

 

반복문을 돌 때 배열의 값을 바뀌면 문제가 발생하는 이유는 1이 0이되고, 0이 1이 되서 발생한다.

 

그렇다면 1)에서 변경되는 값을 임의의 수로 바꿔 canGo()메소드에서 갈 수 있는 값으로 추가하고,

2)에서 변경되는 값을 '1과 위에서 설정한 임의의 수'만 아니면 세지 않게 된다.

 

따라서 1)로 변경되는 값은 2로 설정한 다음 canGo에 추가해주고 2)로 변경되는 값은 3으로 설정해준다.

이렇게 하면 배열에는 변경이 일어나지 않은 0, 1 / 0으로 변경될 2/ 1로 변경될 3 이 남아있게 된다.

 

이 값들을 적절히 변환하면 답이 나오게 된다.

정리

인메모리 시간 안에 배열을 바꾸는 방법