백준 16920번 확장 게임

문제

구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.

게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.

각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.

모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.

입력

첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S1, S2, ...SP가 주어진다.

다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.

모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.

출력

플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.

제한

• 1 ≤ N, M ≤ 1,000
• 1 ≤ P ≤ 9
• 1 ≤ Si ≤ 109

 

로직은 직관적으로 구현하면 됨.

착각하기 쉬운 것은 최대 이동거리를 그 경로 전체를 포함하는지 도착 지점만인지 잘 생각.

그리고 같은 로직인데 후 이동 처리에서 반례가 발생하는 듯 하다.

 

그래서 최대 이동거리 조건을 앞에 넣어 주는 것으로 해결.

#include<iostream>
#include <string.h>
#include<string>
#include<queue>
#include <vector>
#include<map>

using namespace std;
int N, M, P;
int d[9];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int cont[9];
char arr[1000][1000];

int main(int argc, char** argv)
{
	cin >> N >> M >> P;
	for (int i = 0; i < P; i++)
	{
		cin >> d[i];
	}

	queue<pair<int, int> > que[9];
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] >= '1' && arr[i][j] <= '9')
			{
				que[arr[i][j] - '1'].push({ i,j });
				cont[arr[i][j] - '1']++;
			}
		}
	}


	while (1)
	{
		bool flag = false;
		for (int i = 0; i < P; i++)
		{
			int len = d[i];
			while (!que[i].empty() && len--)
			{
				int size = que[i].size();
				for (int j = 0; j < size; j++)
				{
					int y = que[i].front().first;
					int x = que[i].front().second;
					que[i].pop();

					for (int k = 0; k < 4; k++)
					{
						int newy = y + dy[k];
						int newx = x + dx[k];
						if (newy >= 0 && newy < N && newx >= 0 && newx < M)
						{
							if (arr[newy][newx] == '.')
							{
								que[i].push({ newy,newx });
								arr[newy][newx] = '1' + i;
								cont[i]++;
								flag = true;
							}
						}
					}

				}
			}
			
		}
		if (!flag)
		{
			break;
		}
	}

	

	for (int i = 0; i < P; i++)
	{
		cout << cont[i] << " ";
	}
	cout << endl;
}