본문 바로가기
알고리즘/백준

백준 17232 생명 게임 (JAVA 자바 풀이) | 누적합 배열

by Renechoi 2023. 7. 3.

백준 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 '.';
   }
}

 

 

 

반응형