[Matrix][Medium] 289. Game of Life

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

 

Q. 2차 정수 행렬 board가 주어진다. 1이 live, 0이 dead를 의미할 때, 다음에 의해 다음 상태를 구하라. 

 - live cell일 시, 주변에 live cell이 2개보다 적다면 dead 된다. 

 - live cell일 시, 주변에 live cell이 2개 혹은 3개 라면 live cell이 된다. 

 - live cell일 시, 주변에 3개 이상의 live cell이 있다면 dead cell이 된다. 

 - dead cell일 시, 주변에 3개의 live cell이 있다면 live cell이 된다. 

 추가 메모리 할당을 하지 말아라. 

 

 

Solution. 

 우선 문제 해석을 정확하게 하자. 

 

 그리고, 추가 버퍼를 사용하지 않을 시, 

 cell의 상태가 로직을 processing함에 따라 변하므로, 바로 답을 write 하면 안된다. 

 다만, 이전 상태가 이후 상태값을 포함하는 다른 값으로 치환하면 간단해 진다. 

 

 변환 작업을 마친 후, 

 다른 제 3의 값으로 치환된 cell들에 대해, 변화 후의 정보로 1 또는 0으로 재 변환 하면 될 것이다. 

 

 문제 자체의 해석이 된다면, 그 이후는 큰 어려움이 없을 것이다. 

 

 

int checkBoarders(int[][] board, int x, int y)
{
    int live = 0;

    // up
    if(y>0 && (board[y-1][x]==1 || board[y-1][x]==3))
        ++live;
    // down
    if(y<board.Length-1 && (board[y+1][x]==1 || board[y+1][x]==3))
        ++live;
    // left 
    if(x>0 && (board[y][x-1]==1 || board[y][x-1]==3))
        ++live;
    // right
    if(x<board[0].Length-1 && (board[y][x+1]==1 || board[y][x+1]==3))
        ++live;

    // left up
   if(x>0 && y>0 && (board[y-1][x-1]==1 || board[y-1][x-1]==3))
        ++live;
    // right up
    if(x<board[0].Length-1 && y>0 && (board[y-1][x+1]==1 || board[y-1][x+1]==3))
        ++live;
    // left down
    if(x>0 && y<board.Length-1 && (board[y+1][x-1]==1 || board[y+1][x-1]==3))
        ++live;
    // right down
    if(x<board[0].Length-1 && y<board.Length-1 && (board[y+1][x+1]==1 || board[y+1][x+1]==3))
        ++live;

    if(board[y][x] == 0)
    {
        if(live == 3)           return 1;
    }
    else if(board[y][x] == 1)
    {
        if(live < 2)            return 0;
        if(live==2 || live==3)  return 1;
        if(live>3)              return 0;
    }
    return board[y][x];
}
public void GameOfLife(int[][] board) 
{
    for(int y = 0; y < board.Length; ++y)
    {
        for(int x = 0; x < board[0].Length; ++x)
        {
            int next = checkBoarders(board, x, y);

            switch(board[y][x])
            {
            case 0:     board[y][x] = next==1 ? 2 : board[y][x];    break;  // 0 -> 1
            case 1:     board[y][x] = next==0 ? 3 : board[y][x];    break;  // 1 -> 0
            default:    break;
            }
        }
    }  

    for(int y = 0; y < board.Length; ++y)
    {
        for(int x = 0; x < board[0].Length; ++x)
        {
            if(board[y][x] == 2)
                board[y][x] = 1;
            else if(board[y][x] == 3)
                board[y][x] = 0;
        }
    }
}

 

결과. 조금 더 최적화의 여지는 있어 보인다.