백준 17232 생명 게임 (JAVA 자바 풀이)
초기 제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
int T = Integer.parseInt(stringTokenizer.nextToken());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int K = Integer.parseInt(stringTokenizer.nextToken());
int A = Integer.parseInt(stringTokenizer.nextToken());
int B = Integer.parseInt(stringTokenizer.nextToken());
char[][] board = new char[N + K + 2][N + K + 2];
char[][] boardS = new char[N + K + 2][N + K + 2];
for (int i = 0; i < N; i++) {
String status = bufferedReader.readLine();
for (int j = 0; j < N; j++) {
board[i + K][j + K] = status.charAt(j);
}
}
while (T-- > 0) {
for (int i = 0 + K; i < board.length - 2; i++) {
for (int j = 0 + K; j < board[i].length - 2; j++) {
// i, j => 현재 => 주위 탐색
int count = searchNeighbors(board, i, j, K);
// 상태 업데이트
boardS[i][j] = validate(A, B, count, board[i][j]);
}
}
copy(boardS, board);
// board = boardS;
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
stringBuilder.append(board[i + K][j + K]);
}
stringBuilder.append("\n");
}
System.out.print(stringBuilder);
}
private static int searchNeighbors(char[][] board, int i, int j, int K) {
int count = 0;
for (int x = i - K; x <= i + K; x++) {
for (int y = j - K; y <= j + K; y++) {
if (x == i && y == j) {
continue;
}
if (board[x][y] == '*') {
count++;
}
}
}
return count;
}
private static void copy(char[][] from, char[][] to) {
for (int i = 0; i < from.length; i++) {
for (int j = 0; j < from[i].length; j++) {
to[i][j] = from[i][j];
}
}
}
private static char validate(int a, int b, int count, char current) {
if ((current == '\u0000' || current == '.') && count > a && count <= b) {
return '*';
}
if ((current == '*') && count >= a && count <= b) {
return '*';
}
return '.';
}
}
문제는 길지만 한번 이해하고나면 그 다음부터는 문제 자체가 어렵지는 않다.
주의해야 할 포인트는 다음과 같다고 생각한다.
1. 주위에 대한 정의
-> 그대로 구현해주면 되지만 자신을 포함하지 않아야 함
2. 주위 탐색을 위한 보정값 설정
-> 처음 배열을 만들 때 애초에 크게 만들 것인지, 탐색하면서 보정된 값으로 탐색할 것인지 결정
3. 바둑판을 업데이트 하는 방식
-> 초기 방식에서는 카피가 필요했다.
4. 시간복잡도를 해결하는 방법
-> 누적합 배열 사용
초기 코드에서 바둑판을 업데이트하는 부분에서 원본을 S배열에 대입하면 동기화되어 움직인다. 문제의 요구 사항은 한 페이스가 끝날 때마다 생명의 변화를 기록해야하기 때문에 이렇게 하면 원하는 답을 많이 빗나간다.
초기 제출한 코드로 문제에서 제시된 예시 답안은 제대로 출력했지만 문제가 있었다.
첫 번째는 시간 복잡도이다.
위와 같은 코드로 풀이시 T 반복문 내에서 N*M 반복되면서 또 주변 탐색에서 N*M번의 반복이 이루어지므로 O(T * N*M * N*M), 즉 O(N^5) 이므로 시간 초과를 받게 될 것이다.
T 시간의 반복문과 바둑판 내의 점들에 대한 탐색
while (T-- > 0) {
for (int i = 0 + K; i < board.length - 2; i++) {
for (int j = 0 + K; j < board[i].length - 2; j++) {
현재 점에 대한 주위 탐색
// i, j => 현재 => 주위 탐색
int count =0;
for (int k= i-1; k<=i+1;k++){
for (int l= j-1; l<=j+1; l++){
if (k==i && l == j){
continue;
}
if (board[k][l] == '*'){
count++;
}
}
}
따라서 주위 탐색을 하는 부분의 시간 복잡도를 낮추어야 한다. 누적합 배열을 사용하면 이 부분의 시간 복잡도를 O(1)로 낮출 수 있다.
두 번째 문제점은 보정값을 설정한 부분이다. K 값에 따라 앞뒤로 탐색을 하는 동안 필연적으로 주어진 바둑판 범위를 벗어난 탐색이 이루어지게 된다. 이를 보정하기 위해서 아예 처음부터 바둑판 크기를 K 만큼 키워주는 방식으로 했었다.
그런데 이렇게 하면 뒤에 계산마다 계속 K 값을 신경써주면서 계산해야 해서 너무 머리가 복잡해졌다.
누적합 배열을 사용하기
누적합 배열을 이용하면 전체 배열의 누적합을 구해놓은 상태에서 특정 범위 구간의 합을 구할 수 있다.
2차원 배열에서 누적합은 다음과 같이 구한다.
private static int[][] calculateTwoDimensionalRangeSum(int[][] numbers) {
int[][] Snumbers = new int[numbers.length][numbers.length];
for (int i = 1; i < numbers.length; i++) {
for (int j = 1; j < numbers.length; j++) {
Snumbers[i][j] = numbers[i][j] + Snumbers[i - 1][j] + Snumbers[i][j - 1] - Snumbers[i - 1][j - 1];
}
}
return Snumbers;
}
private static int calculateSumWithRangeSum(int x1, int y1, int x2, int y2, int[][] Snumbers) {
return Snumbers[x2][y2] - Snumbers[x2][y1 - 1] - Snumbers[x1 - 1][y2] + Snumbers[x1 - 1][y1 - 1];
}
이 방식을 적용하여 *을 1로 친다면 k값이 적용된 범위 내에서 *의 유무를 카운트할 수 있다. 이때 매번 누적합 배열은 페이스 별로 한번만 구해놓으면 되며, 특정 범위를 구할 때 시간 복잡도는 상수이므로 매번 반복문을 돌면서 탐색할 필요가 사라진다. 결과적으로 N*M의 시간 복잡도를 제거한다.
풀이에서 누적합 배열은 다음과 같이 구하였다.
private static int[][] getAccumulatedRangeSum(char[][] board) {
int[][] boardS = new int[board.length - 1 + 1][board[0].length - 1 + 1];
for (int i = 1; i <= board.length - 1; i++) {
for (int j = 1; j <= board[0].length - 1; j++) {
boardS[i][j] = convertToInt(board[i][j]) + boardS[i - 1][j] + boardS[i][j - 1] - boardS[i - 1][j - 1];
}
}
return boardS;
}
private static int convertToInt(char mark) {
if (mark == '*') {
return 1;
}
return 0;
}
이후 K값이 적용된 범위를 갖고 해당하는 구간에 얼마나 많은 *이 있는지를 카운트해보자.
private static int searchNeighbors(int[][] boardS, int i, int j, int K) {
int x1 = Math.max(i - K, 1);
int y1 = Math.max(j - K, 1);
int x2 = Math.min(i + K, boardS.length - 1);
int y2 = Math.min(j + K, boardS[0].length - 1);
return boardS[x2][y2] - boardS[x2][y1 - 1] - boardS[x1 - 1][y2] + boardS[x1 - 1][y1 - 1];
}
범위를 주는 부분에서 Math.max와 min 함수를 이용해 보정한다. 즉, 범위 바깥을 왼쪽과 위쪽에서 넘어갈 경우 1로 설정하고, 오른쪽과 아래쪽으로 넘어갈 경우 주어진 바둑판의 마지막 인덱스를 설정한다.
이렇게 하여 K 값이 적용된 범위를 보정할 수 있다. 이후에는 구한 누적 배열에서 특정 인덱스를 구하는 방식에 따라 구하면 된다.
구한 count로 업데이트는 다음과 같이 한다.
board[i][j] = update(A, B, count, board[i][j]);private static char update(int a, int b, int count, char current) {
if ((current == '*')) {
count--;
if (count >= a && count <= b) {
return '*';
}
}
if ((current == '.') && count > a && count <= b) {
return '*';
}
return '.';
}
이 부분은 문제의 요구사항을 그대로 따른 부분이다. 주의할 점은 눚거배열은 자기 자신의 대한 값 역시도 카운트를 했으므로, 해당 값을 빼주기위한 count--; 부분이다.
💡 코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
int T = Integer.parseInt(stringTokenizer.nextToken());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int K = Integer.parseInt(stringTokenizer.nextToken());
int A = Integer.parseInt(stringTokenizer.nextToken());
int B = Integer.parseInt(stringTokenizer.nextToken());
char[][] board = new char[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
String input = bufferedReader.readLine();
for (int j = 1; j <= M; j++) {
board[i][j] = input.charAt(j - 1);
}
}
while (T-- > 0) {
// 누적합 배열 구하기
int[][] boardS = getAccumulatedRangeSum(board);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
// i, j => 현재 => 주위 탐색
int count = searchNeighbors(boardS, i, j, K);
// 상태 업데이트
board[i][j] = update(A, B, count, board[i][j]);
}
}
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
stringBuilder.append(board[i][j]);
}
stringBuilder.append("\n");
}
System.out.print(stringBuilder);
}
private static int[][] getAccumulatedRangeSum(char[][] board) {
int[][] boardS = new int[board.length - 1 + 1][board[0].length - 1 + 1];
for (int i = 1; i <= board.length - 1; i++) {
for (int j = 1; j <= board[0].length - 1; j++) {
boardS[i][j] = convertToInt(board[i][j]) + boardS[i - 1][j] + boardS[i][j - 1] - boardS[i - 1][j - 1];
}
}
return boardS;
}
private static int convertToInt(char mark) {
if (mark == '*') {
return 1;
}
return 0;
}
private static int searchNeighbors(int[][] boardS, int i, int j, int K) {
int x1 = Math.max(i - K, 1);
int y1 = Math.max(j - K, 1);
int x2 = Math.min(i + K, boardS.length - 1);
int y2 = Math.min(j + K, boardS[0].length - 1);
return boardS[x2][y2] - boardS[x2][y1 - 1] - boardS[x1 - 1][y2] + boardS[x1 - 1][y1 - 1];
}
private static char update(int a, int b, int count, char current) {
if ((current == '*')) {
count--;
if (count >= a && count <= b) {
return '*';
}
}
if ((current == '.') && count > a && count <= b) {
return '*';
}
return '.';
}
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2295 세 수의 합 (JAVA 자바 풀이) (1) | 2023.07.04 |
|---|---|
| 백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이) (0) | 2023.07.03 |
| 백준 19951 태상이의 훈련소 생활 (JAVA 자바 풀이) (0) | 2023.07.02 |
| 백준 10811 바구니 뒤집기 (JAVA 자바 풀이) (0) | 2023.07.02 |
| 백준 10813 공 바꾸기 (JAVA 자바 풀이) (0) | 2023.07.02 |
