백준 17232번: 생명 게임 [구간합][누적합][DP][동적프로그래밍][시뮬레이션][구현] -Java

<https://www.acmicpc.net/problem/17232

17232번: 생명 게임

어려웠다 ㅎㅎ

구간합이 필요한 부분은 (1,1)부터 (i,j)까지의 모든 생명의 수의 누적합이다.

그리고 난 다음에 주위 범위대로 범위를 계산하면 되는 것..

나는 해당범위 생명수를 구간합으로 적용을 시켜야할까?에서부터 글러먹었다는..

 

구간합 적용을 하지 않고 일일히 다 for문돌면서 풀면 K=1인 서브태스크1은 해결이 가능하겠지만 2는 시간초과가 날 것이다.

 

<백준 17232번 생명게임 Java코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //세로길이
		int M = Integer.parseInt(st.nextToken()); //가로길이
		int T = Integer.parseInt(st.nextToken()); //관찰시간
		
		char map[][] = new char[N+1][M+1];
		
		st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		for (int i = 1; i < N+1; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for (int j = 1; j < M+1; j++) {
				map[i][j] = str.charAt(j-1);
			}
		}
		
		int sum[][] = new int[N+1][M+1];
		for (int time = 0; time < T; time++) {
			//1. 시간 흐를때마다 다시 누적합 계산
			for (int i = 1; i < N+1; i++) {
				for (int j = 1; j < M+1; j++) {
					sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
					if(map[i][j]=='*')
						sum[i][j]++;
				}
			}
			
			//2. 각각의 좌표 위치의 주위 값 구하기
			for (int i = 1; i < N+1; i++) {
				for (int j = 1; j < M+1; j++) {
					//2-1. 2k+1한 값이 배열범위를 벗어나진 않는지 체크
					int r1 = Math.max(i-K, 1);
					int c1 = Math.max(j-K, 1);
					int r2 = Math.min(i+K, N);
					int c2 = Math.min(j+K, M);
					
					int around = sum[r2][c2] - sum[r2][c1-1] - sum[r1-1][c2] + sum[r1-1][c1-1];
					if(map[i][j]=='*')
						around--;
					//System.out.println(around+", "+map[i][j]);
					//3. 주위의 생명 갯수에 따라 4가지상황 결정
//					생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다.
//					고독 : 만약 현재 칸에 생명이 있고, 주위에 a개 미만의 생명이 있다면 현재 칸의 생명은 외로워서 죽는다.	
//					과밀 : 만약 현재 칸에 생명이 있고, 주위에 b개 초과의 생명이 있다면 현재 칸의 생명은 과밀로 죽는다.
//					탄생 : 만약 현재 칸에 생명이 없고, 주위에 a개 초과 b개 이하의 생명이 있다면 다음 단계에서 현재 칸에 생명이 생긴다.
					if(map[i][j]=='*') {
						if(around < a || around > b)
							map[i][j] = '.';
						else 
							map[i][j] = '*';
					} else {
						if (around > a && around <= b)
							map[i][j] = '*';
						else
							map[i][j] = '.';
					}
				}
			}
		}
		
		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < M+1; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		
	}

}