Problem
n * m
크기의 보드가 주어지고 각 칸에 존재하는 세포가 다음 세대가 되었을 때의 상태를 구하는 문제입니다.
Solution
각 세포는 상하좌우와 대각선까지 해서 총 8 명의 이웃이 있습니다.
문제에 나와있는 세포들의 생존, 사망 조건을 정리하면 다음과 같습니다.
# 살아있는 세포
- 이웃이 2 명 미만이면 사망
- 이웃이 3 명 초과면 사망
- 이웃이 2, 3 명이면 현재 상태 그대로 진행
# 죽은 세포
- 이웃이 3 명이면 생존
- 그 외에는 현재 상태 그대로
단순하게 이중 for 문을 돌면서 8 방향 확인하면 됩니다.
주의해야 할 점은 변경된 세포의 상태를 바로 갱신해버리면 옆에 있는 세포의 조건을 검사할 때 꼬일 수 있다는 점입니다.
임시로 2차원 배열을 선언해서 해결할 수도 있지만 Follow up 에서 in-place 로 해결해보라고 나와있습니다.
board
의 값을 바로바로 갱신하되, 0 과 1 대신에 3 과 2 로 갱신해줍니다.
현재 죽음 - 다음 세대에 살아남 ⇒ 3
현재 생존 - 다음 세대에 죽음 ⇒ 2
이렇게 변경해주면 숫자만 보고 현재 상태와 다음 세대를 알 수 있습니다.
모든 검사가 끝나면 %2
연산으로 상태를 갱신해주면 됩니다.
Java Code
class Solution {
public void gameOfLife(int[][] board) {
int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
int n = board.length, m = board[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int lives = 0;
for (int k = 0; k < 8; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (board[x][y] == 1 || board[x][y] == 2) lives++;
}
if (board[i][j] == 0 && lives == 3) board[i][j] = 3;
if (board[i][j] == 1 && (lives < 2 || lives > 3)) board[i][j] = 2;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] %= 2;
}
}
}
}
'알고리즘 문제 > LeetCode' 카테고리의 다른 글
[LeetCode Easy] Maximum Number of Balloons (Java) (0) | 2021.03.31 |
---|---|
[LeetCode Medium] Binary Tree Level Order Traversal (Java) (0) | 2021.01.03 |
[LeetCode Medium] Odd Even Linked List (Java) (0) | 2021.01.03 |
[LeetCode Medium] Find the Duplicate Number (Java) (0) | 2021.01.02 |
[LeetCode Medium] Group Anagrams (Java) (0) | 2021.01.01 |