[BOJ/Gold 5] 백준 17232 생명 게임(C++)

문제 링크

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

17232번: 생명 게임

 

문제

생명 게임은 수학자 콘웨이(John Horton Conway)가 창안한 게임으로, 바둑판 모양의 격자에 '생명'을 배치하고 그 변화를 관찰하는 게임이다.

<그림1> 자리를 바꾸면서 무한히 움직이는 패턴의 한 예. 출처) 네이버 지식백과

준표는 콘웨이가 창안한 생명 게임에서 사소한 조건을 바꿔 새로운 규칙의 생명 게임을 제안 해보았다.

<그림2>

바둑판의 각 칸은 주위의 영향을 받는데, 주위란 <그림2>에서 색칠한 영역과 같이 현재 칸을 중심으로 둔 한 변의 길이가 (2K + 1) 인 정사각형에서 현재 칸을 제외한 영역을 말한다.

바둑판의 각 칸은 주위에 몇 개의 생명이 존재하는지에 따라 다음 상황이 아래와 같이 결정된다.

1. 생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다.
2. 고독 : 만약 현재 칸에 생명이 있고, 주위에 a개 미만의 생명이 있다면 현재 칸의 생명은 외로워서 죽는다.
3. 과밀 : 만약 현재 칸에 생명이 있고, 주위에 b개 초과의 생명이 있다면 현재 칸의 생명은 과밀로 죽는다.
4. 탄생 : 만약 현재 칸에 생명이 없고, 주위에 a개 초과 b개 이하의 생명이 있다면 다음 단계에서 현재 칸에 생명이 생긴다.

생명은 바둑판을 벗어난 영역에서는 생존할 수 없다.

준표는 N×M 크기의 바둑판에 생명을 뿌리고, T시간 뒤의 생명을 관찰하고자 한다.

입력

첫줄에는 바둑판의 세로길이, 가로길이를 나타내는 두 정수 N과 M, 준표가 바둑판을 관찰하고자 하는 시간 T가 주어진다.

두번째 줄에는 주위의 기준이 되는 정수 K, 각 칸의 다음 상황을 결정하는 정수 a, b가 주어진다.

다음 N개의 줄에 걸쳐 바둑판의 처음 상태가 주어진다. 각 줄은 길이 M의 문자열로 생명이 있는 칸은 '*', 빈칸은 '.'로 주어진다.

출력

N개의 줄에 걸쳐 바둑판의 상태를 출력한다. 각 줄은 길이 M의 문자열로 생명이 있는 칸은 '*', 빈칸은 '.'로 출력한다.

제한

• 1 ≤ N, M ≤ 100
• 1 ≤ T ≤ 300
• 0 ≤ a, b < (2×K+1)2

서브태스크 1 (100점)

• K = 1

서브태스크 2 (40점)

• 1 ≤ K ≤ max(N, M)

예제 입력 1

6 6 7
1 2 3
.*....
..*...
***...
......
......
......

예제 출력 1

......
......
..*...
...**.
..**..
......

알고리즘 분류

• 구현
• 누적 합

풀이

T번에 걸쳐 다음과 같이 진행한다.

1. 2차원 배열의 누적 합을 구한다.

2. 각 칸마다 생명의 합을 구할 범위를 구한다.

3. 범위 내의 생명의 합(자기 자신 제외)을 구하고, 현재 칸이 1일 때에는 생명의 합이 A보다 작거나 B보다 크면 현재 칸은 0이고, A 이상 B 이하라면 그대로 놔둔다. 현재 칸이 0일 때 A 초과 B 이하라면 1이 된다.

마지막으로 T번에 걸쳐 작업을 수행한 후의 상태를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 101
#define LL long long
#define INF 1e9

using namespace std;
int N, M, T, K, A, B;
int MAP[MAX][MAX];
int Sum[MAX][MAX];
int Next[MAX][MAX];

void Input() {
	cin >> N >> M >> T;
	cin >> K >> A >> B;
	for (int i = 1; i <= N; i++) {
		string S;
		cin >> S;
		for (int j = 1; j <= M; j++) {
			if (S[j - 1] == '*') {
				MAP[i][j] = 1;
			}
		}
	}
}

void Settings() {
	while (T--) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				Sum[i][j] = MAP[i][j] + Sum[i][j - 1] + Sum[i - 1][j] - Sum[i - 1][j - 1];
			}
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				int Y1 = max(1, i - K);
				int X1 = max(1, j - K);
				int Y2 = min(N, i + K);
				int X2 = min(M, j + K);
				int Cur = Sum[Y2][X2] - Sum[Y1 - 1][X2] - Sum[Y2][X1 - 1] + Sum[Y1 - 1][X1 - 1] - MAP[i][j];
				if (MAP[i][j] == 1) {
					if ((A > Cur) || (B < Cur)) {
						MAP[i][j] = 0;
					}
					else if ((A <= Cur) && (Cur <= B)) {
						MAP[i][j] = 1;
					}
				}
				else {
					if ((A < Cur) && (Cur <= B)) {
						MAP[i][j] = 1;
					}
				}
			}
		}
	};
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (MAP[i][j] == 1) {
				cout << "*";
			}
			else {
				cout << ".";
			}
		}
		cout << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}