[백준 16920] 확장 게임 (C++)

문제 링크: www.acmicpc.net/problem/16920

16920번: 확장 게임

1. 주의할 점

- BFS()를 통해 퍼트린다

- 최대한 간단하게 구현한다

 

2. 구현

- 한번에 퍼질 수 있는 정도를 Len[] 배열에 담는다

- 10개짜리 Queue를 생성하여 각 숫자에 해당하는 경우에만 포함하도록 한다

- 입력받을 때, 해당 지역이 성이면 개수를 센다

- BFS() 함수를 통해 1부터 P번까지의 Queue를 순서대로 퍼트린다

- Arr[][] 배열만을 사용하며, 다음 칸으로 이동이 가능하면 Arr[][] 배열을 바꾼다. 이 과정을 Queue 안의 원소수 * Len[]만큼 수행한다

- 모든 사람들이 퍼질때까지 위의 작업을 반복한다

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int y, x;
};
info tmp;
int num, result, dig;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int row, col, p;
int area[10];
int len[10];
char arr[1000][1000];
queue<info> q[10];

void bfs() {
	while (1) {
		for (int t = 1; t <= p; t++) {
			int dist = len[t];
			while (!q[t].empty() && dist--) {
				int qs = q[t].size();
				for (int i = 0; i < qs; i++) {
					int cx = q[t].front().x;
					int cy = q[t].front().y;
					q[t].pop();
					for (int k = 0; k < 4; k++) {
						int nx = cx + dx[k];
						int ny = cy + dy[k];
						if (nx >= 0 && ny >= 0 && nx < col && ny < row && arr[ny][nx] == '.') {
							arr[ny][nx] = t + '0';
							q[t].push({ ny,nx });
							area[t]++;
						}
					}
				}
			}
		}
		bool finish = true;
		for (int i = 1; i <= p; i++) {
			if (!q[i].empty()) {
				finish = false;
				break;
			}
		}
		if (finish) break;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col >> p;
	for (int i = 1; i <= p; i++) 
		cin >> len[i];
	
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			if ('1' <= arr[i][j] && arr[i][j] <= '9') {
				q[arr[i][j] - '0'].push({ i,j });
				area[arr[i][j] - '0']++;
			}
		}
	bfs();
	for (int i = 1; i <= p; i++)
		cout << area[i] << " ";
	return 0;
}