BOJ17232 생명게임*

 

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

17232번: 생명 게임

 

 

2차원 누적합을 이용한 시뮬레이션 구현 문제이다. 구현시 실수하지 않도록 주의하자. min(머시기,m)으로 해야하는데 min(머시기,n)으로 한걸 못찾아서 시간을 버렸다.

 

 

범위를 벗어나는지 체크를 if 조건문이 아닌 min, max를 이용하는 것도 좋은 방법이다.

import java.util.*;
import java.io.*;
public class Main
{   
    static String[][] map;
    static int[][] acc;
    static int k;
    static int n;
    static int m;
    static int a;
    static int b;
    
    
    
    public static int checkType(int x, int y){
        //0:생존, 1:고독, 2:과밀, 3:탄색 -1: 기타
        int life = countLife(x+1,y+1);
        if(map[x][y].equals("*")){
            if(life>=a && life<=b) return 0;
            if(life<a) return 1;
            if(life>b) return 2;
        }
        if(map[x][y].equals(".")){
            if(life> a&&life<=b ) return 3;
        }
        return -1;    
        
    }
    
    public static int countLife(int x,int y){
        int x1=Math.max(x-k,1);
        int y1=Math.max(y-k,1);
        int x2=Math.min(x+k,n);
        int y2=Math.min(y+k,m);
        if(map[x-1][y-1].equals("*")) {
            return acc[x2][y2]-acc[x2][y1-1] - acc[x1-1][y2] + acc[x1-1][y1-1] - 1;    
        }
        return acc[x2][y2]-acc[x2][y1-1] - acc[x1-1][y2] + acc[x1-1][y1-1];
    }
    
    
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    String[] input1 = br.readLine().split(" ");
	    n = Integer.valueOf(input1[0]);
	    m = Integer.valueOf(input1[1]);
	    int t = Integer.valueOf(input1[2]);
	    
	    map= new String[n][m];
	    acc = new int[n+1][m+1];
	    
	    String[] input2 = br.readLine().split(" ");
	    k = Integer.valueOf(input2[0]);
	    a = Integer.valueOf(input2[1]);
	    b = Integer.valueOf(input2[2]);
	    
	    for(int i=0;i<n;i++){
	        map[i]=br.readLine().split("");
	    }
	    
	    
	    
	    while(t-->0){
	        String[][] newMap = Arrays.copyOf(map,map.length);
	        for(int i=1; i<n+1;i++){
	            for(int j=1; j<m+1;j++){
	                int curLife = map[i-1][j-1].equals("*")?1:0;
	                acc[i][j] = acc[i-1][j]+acc[i][j-1]-acc[i-1][j-1]+curLife;
	            }
	        }
	        
	        for(int i=0;i<n;i++){
	            for(int j=0;j<m;j++){
	                switch(checkType(i,j)){
	                    case 0:
	                        break;
	                    case 1:
	                        newMap[i][j]=".";
	                        break;
	                    case 2:
	                        newMap[i][j]=".";
	                        break;
	                    case 3:
	                        newMap[i][j]="*";
	                        break;
	                    default:
	                        break;
	                }
	            }
	        }
	        map = newMap;
	    }    
	    
	   for(String[] sArr :map){
    	        for(String s: sArr){
    	            bw.write(s);
    	       }
    	    bw.write("\n");
    	    
	        }
	    

		bw.flush();
	
	    }
}

 

import java.util.Scanner;

class Main
{
    static int[][] getPrefixSum(char[][] map) {
        int N = map.length - 1;
        int M = map[0].length - 1;
        int[][] acc = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) {
                int alive = (map[i][j] == '*' ? 1 : 0);
                acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + alive;
            }
        return acc;
    }

    static int getRangeSum(int[][] acc, int r, int c, int K) {
        int r1 = Math.max(r - K, 1);
        int c1 = Math.max(c - K, 1);
        int r2 = Math.min(r + K, acc.length - 1);
        int c2 = Math.min(c + K, acc[0].length - 1);
        return acc[r2][c2] - acc[r1 - 1][c2] - acc[r2][c1 - 1] + acc[r1 - 1][c1 - 1];
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();
        int K = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();

        char[][] map = new char[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String rowMap = sc.next();
            for (int j = 1; j <= M; j++)
                map[i][j] = rowMap.charAt(j - 1);
        }

        while (T-- > 0) {
            int[][] acc = getPrefixSum(map);
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= M; j++) {
                    int nearAlive = getRangeSum(acc, i, j, K);
                    if (map[i][j] == '*') {
                        nearAlive--;
                        if (nearAlive < A || B < nearAlive)
                            map[i][j] = '.';
                    }
                    else if (A < nearAlive && nearAlive <= B)
                        map[i][j] = '*';
                }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++)
                System.out.print(map[i][j]);
            System.out.println();
        }
    }
}