LeetCode 289. Game of Life 자바 문제 풀이

문제

Game of Life - LeetCode

문제 해결 방법

-조건

주위 live cell의 개수가 2보다 작으면 dead

주위 live cell의 개수가 2와 같으면 유지

주위 live cell의 개수가 3과 같으면 live

주위 live cell의 개수가 3보다 많으면 dead

-즉 이미 죽었느냐 살았느냐 보다는 주위에 있는 live cell의 개수를 세는게 중요함

-보드의 끝부분에 있을때는 없는 부분에 주의하여, null pointer가 안나도록 해야함.

-이미 업데이트된 정보를 다시 검색하지 않으므로, 새로운 2D어레이를 생성해서 사용하는게 좋음.

시간복잡도: O(mn), 공간복잡도: O(mn)

https://github.com/eunhanlee/LeetCode_289.GameofLife.git

class Solution {
    public void gameOfLife(int[][] board) {
        int[][] result = new int[board.length][board[0].length];

        for (int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                int liveCells=getAroundLiveCells(i,j,board);
                if(liveCells<=2) result[i][j]=0;
                if(liveCells==2) result[i][j]=board[i][j];
                if(liveCells==3) result[i][j]=1;
                if(liveCells>3) result[i][j]=0;

            }

        }
        for (int i = 0; i < result.length; i++) {
            board[i] = result[i].clone();
        }
    }

    public static int getAroundLiveCells(int i, int j, int[][]board){
        int counter=0;
        if ((i - 1 > -1)) {
            if ((j - 1 > -1)) {
                if (board[i - 1][j - 1] == 1) counter++;
            }
            if ((j + 1 < board[0].length)) {
                if (board[i - 1][j + 1] == 1) counter++;
            }
            if (board[i - 1][j] == 1) counter++;
        }
        if ((j - 1 > -1)) {
            if (board[i][j - 1] == 1) counter++;
        }
        if (j + 1 < board[0].length) {
            if (board[i][j + 1] == 1) counter++;
        }
        if (i + 1 < board.length) {
            if (j - 1 > -1) {
                if (board[i + 1][j - 1] == 1) counter++;
            }
            if (j + 1 < board[0].length) {
                if (board[i + 1][j + 1] == 1) counter++;
            }
            if (board[i + 1][j] == 1) counter++;
        }
        return counter;
    }
}

이제 위 코드를 최적화 하고 주석을 추가합니다

class Solution {
    /**
     * 게임 오브 라이프의 규칙에 따라 보드를 다음 상태로 업데이트합니다.
     *
     * @param board 현재 게임 상태를 나타내는 2차원 배열입니다.
     */
    public void gameOfLife(int[][] board) {
        int[][] result = new int[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 현재 셀 주변의 살아있는 셀 개수를 세어줍니다.
                int liveCells = getAroundLiveCells(i, j, board);

                // 게임의 규칙을 적용합니다.
                if (liveCells <= 2)
                    result[i][j] = 0;
                else if (liveCells == 2)
                    result[i][j] = board[i][j];
                else if (liveCells == 3)
                    result[i][j] = 1;
                else
                    result[i][j] = 0;
            }
        }

        // 새로운 상태로 원래 보드를 업데이트합니다.
        for (int i = 0; i < result.length; i++) {
            board[i] = result[i].clone();
        }
    }

    /**
     * 주어진 셀 주변에 살아있는 셀의 개수를 세어줍니다.
     *
     * @param i     현재 셀의 행 인덱스입니다.
     * @param j     현재 셀의 열 인덱스입니다.
     * @param board 현재 게임 상태를 나타내는 2차원 배열입니다.
     * @return 현재 셀 주변의 살아있는 셀의 개수입니다.
     */
    public static int getAroundLiveCells(int i, int j, int[][] board) {
        int counter = 0;

        // 이웃하는 셀들을 반복합니다.
        for (int x = Math.max(0, i - 1); x <= Math.min(board.length - 1, i + 1); x++) {
            for (int y = Math.max(0, j - 1); y <= Math.min(board[0].length - 1, j + 1); y++) {
                // 현재 셀을 건너뜁니다.
                if (x == i && y == j)
                    continue;

                // 살아있는 셀을 카운트합니다.
                if (board[x][y] == 1)
                    counter++;
            }
        }

        return counter;
    }
}

Follow up 질문

공간복잡도를 O(1)으로 새로운 2D 어레이를 쓰지 않고 문제를 풀어보라는 질문입니다. 이런경우에는 2와 3을 사용하여, 변환된 수화 변환 전 숫자를 표현합니다.

다시말해, 2와 3은 셀 상태의 임시 표시를 위한 값으로 사용됩니다.

• 2: 살아있는 상태에서 죽은 상태로 변경된 세포를 나타냅니다.
  • 이 값은 조건에 따라서 현재 살아있는 세포가 다음 세대에서 죽은 상태로 변경되어야 함을 표시하기 위해 사용됩니다.
• 3: 죽은 상태에서 살아있는 상태로 변경된 세포를 나타냅니다.
  • 이 값은 조건에 따라서 현재 죽은 세포가 다음 세대에서 살아있는 상태로 변경되어야 함을 표시하기 위해 사용됩니다.

게임의 규칙에 따라 현재 상태에서 다음 세대로 진행할 때, 모든 세포의 상태를 한꺼번에 업데이트하려면, 동일한 배열에서 세포의 상태를 변경하면서 원래 상태와 구분하기 위한 임시 값이 필요합니다. 따라서, 2와 3이 임시 상태를 나타내기 위한 값으로 사용되었습니다.

이후에 임시 상태를 실제 상태로 변경하는 단계에서는, 2와 3을 2로 나눈 나머지를 취함으로써, 2와 3을 모두 1로 변경하여 실제 상태를 나타내게 됩니다.

class Solution2 {
    
    /**
     * 게임의 진행 상태를 업데이트하는 메서드입니다.
     * 
     * @param board 게임 보드를 나타내는 2차원 배열
     */
    public void gameOfLife(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int liveCells = getAroundLiveCells(i, j, board);
                if (board[i][j] == 1 && (liveCells < 2 || liveCells > 3)) board[i][j] = 2; // 살아있는 상태에서 주변 살아있는 세포 수가 2 미만 또는 3 초과일 경우, 세포를 죽은 상태로 변경
                if (board[i][j] == 0 && liveCells == 3) board[i][j] = 3; // 죽은 상태에서 주변 살아있는 세포 수가 정확히 3일 경우, 세포를 살아있는 상태로 변경
            }
        }

        // 임시 상태를 실제 상태로 변경
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] %= 2;
            }
        }
    }

    /**
     * 주어진 위치의 세포 주변에 있는 살아있는 세포의 수를 반환하는 메서드입니다.
     * 
     * @param i     현재 위치의 행 인덱스
     * @param j     현재 위치의 열 인덱스
     * @param board 게임 보드를 나타내는 2차원 배열
     * @return 주어진 위치의 세포 주변에 있는 살아있는 세포의 수
     */
    public static int getAroundLiveCells(int i, int j, int[][] board) {
        int counter = 0;

        // 인접한 세포 중 살아있는 세포 수를 계산
        // 2는 살아있는 상태에서 죽은 상태로 변경된 세포를 의미
        // 3은 죽은 상태에서 살아있는 상태로 변경된 세포를 의미
        for (int x = Math.max(0, i - 1); x <= Math.min(board.length - 1, i + 1); x++) {
            for (int y = Math.max(0, j - 1); y <= Math.min(board[0].length - 1, j + 1); y++) {
                if (x == i && y == j) continue; // 자기 자신의 세포는 제외
                if (board[x][y] == 1 || board[x][y] == 2)
                    counter++; // 살아있는 세포와 업데이트 이전에 살아있던 세포를 모두 카운트
            }
        }
        return counter;
    }
}

추가 질문

Java 메소드 매개변수 참조 변경 불가: 왜 그럴까요?