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

백준의 확장게임(16920) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

1) 문제를 보면, 성을 하나씩 확장해 나가야 하는 문제이다. 초기에는 1개 모든 플레이어가 한 개 이상의 성을 가지고 있

    으며, 더 이상 확장을 할 수 없을 때 게임이 끝나게 된다.

    본인은 이 문제를 각 성이 확장해 나가는 것을 BFS로 확장할 수 있는 칸 수 만큼 Count해주면서 순서대로 확장하는

    방식으로 구현해 보았다.

    따라서, 가장 초기의 성을 가지고 BFS 연산을 해야하기 때문에 입력 받을 때 성의 위치를 저장해주어야 한다.

    이 부분을 위해서 본인은 Queue배열을 사용해 주었다. Queue[MAX]; 이렇게 !

   Queue에서는 총 3개의 값을 관리해 주었다. (x, y) 좌표와 움직일 수 있는 거리. 여기서 움직일 수 있는 거리라는 것은

   각 플레이어마다 확장할 수 있는 칸 수를 의미한다.

  

2) 그렇다면 BFS에서 해줘야 할 일을 알아보자. 사실, DFS로 구현했다면 매개변수로 Depth를 이용해서, 플레이어마다

     확장할 수 있는 칸수를 쉽게 계산하면서 확장했을 텐데, BFS라서 살짝 헷갈리는 부분이 있었다.

     BFS에서 2개의 Queue를 사용해주었다. 기존에 입력할 때 부터 사용했던 Queue와 BFS탐색을 할 때에는 NQ라는

    Next_Queue를 하나 더 사용해 주었다. NQ를 사용한 이유는 성들의 효율적인 관리를 위함이다.

    먼저 코드를 보고 설명을 이어서 보도록 하자.

bool BFS(int Idx)
{
	bool Temp_Flag = false;
	queue<pair<pair<int, int>, int>> NQ = Q[Idx];
	while (NQ.empty() == 0)
	{
		int x = NQ.front().first.first;
		int y = NQ.front().first.second;
		int Cnt = NQ.front().second;
		NQ.pop();

		if (Cnt == Move_Area[Idx]) Q[Idx].pop();	
		
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nCnt = Cnt;

			if (nCnt == 0) break;
			if (nx >= 0 && ny >= 0 && nx < N && ny < M)
			{
				if (MAP[nx][ny] == '.')
				{
					MAP[nx][ny] = Idx + '0';
					Count_Area[Idx]++;
					Q[Idx].push(make_pair(make_pair(nx, ny), Move_Area[Idx]));
					NQ.push(make_pair(make_pair(nx, ny), nCnt - 1));
					Temp_Flag = true;
				}
			}
		}
	}
	return Temp_Flag;
}

    이게 본인의 BFS부분이다. 가장 먼저 보면, NQ에 Q를 그대로 옮겨주는 과정이 있다.

    그렇다면 여기서 NQ와 Q의 역할에 대해서 확실히 알아보고 넘어가자.

    입력 때 부터 사용한 Queue(본문 : Q[Idx]) 는 현재 Idx번 플레이어의 확장 될 성들만 저장해 놓는 것이다.

    예를 들어서, 1번 플레이어가 성을 확장한번 한 후에, 한 바퀴를 돌고 다시 1번 플레이어가 확장할 차례로 돌아왔다고 생각해보자.

    그렇다면 여기서, 1번 플레이어가 초기에 가지고 있는 성들부터 다시 일일이 확장해 나가야 할 필요가 있을까?? 아니다. 그건 오히려

    시간 낭비일 것이다. 이미, 한번 확장을 했기 때문에, 이 다음에 확장할 때에는 '확장된 성들'에서 확장을 시키면 되는 것이다.

    즉, 이 새롭게 '확장된 성들'을 저장해 놓는 큐가 Queue이다.

    그렇다면 Next_Queue(본문 : NQ)는 무엇일까 ??

    그냥 간편한 연산을 위한것이다. 아래 그림을 한번 생각해보자.

     이런 그림이 있다고 생각해보자.

      플레이어1 이 2칸씩 확장 가능한 상태라고 생각해보면 빨강칸은

      1칸 확장했을 때 갈 수 있는 곳, 파랑색은 2칸 확장했을 때 갈 수 있는 곳을

      의미한다. 즉, 플레이어1의 자신의 턴이 한바퀴 돌고 돌아오게 된다면

      저 그림에서 빨강칸 + 파랑칸에 대해서만 확장을 해주면 되는 것이다.

      가장 초기인 (0, 0)에 대해서는 확장을 해줄 필요가 없다.

      따라서, 위의 코드 중간에 보면

      if(Cnt == Move_Area[Idx]) Q[Idx].pop(); 이라는 구문이 있는데

      이 구문이 이미 확장한 원래의 성을, Queue에서 pop해주는 것이다.

 

   NQ는 이렇게 성을 관리하기 위해서 사용해준 것이다.

 

3) 그렇다면 이제 마무리 단계만 남았다.

    우리는 모든 플레이어가 더 이상 성을 확장할 수 없을 때까지 이 과정을 반복해줘야 한다.

    따라서 본인은, Flag[]라는 bool형 배열을 만들어서, x번플레이어가 확장할 수 없는 경우 Flag[x] = false 로

    표시해주었고, Flag[모든플레이어] = false가 되는순간 무한루프를 종료할 수 있도록 무한루프 안에서

    실행시켜 주었다.

 

[ 소스코드 ]

[ 소스코드 ]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

#define endl "\n"
#define MAX 1000
#define P_MAX 10
using namespace std;

int N, M, P;
int Move_Area[P_MAX];
int Count_Area[P_MAX];
bool Visit[MAX][MAX];
bool Flag[P_MAX];
char MAP[MAX][MAX];
queue<pair<pair<int, int>, int>> Q[P_MAX];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void Input()
{
	cin >> N >> M >> P;
	for (int i = 1; i <= P; i++) cin >> Move_Area[i];
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> MAP[i][j];
			if ('1' <= MAP[i][j] && MAP[i][j] <= '9')
			{
				Q[MAP[i][j] - '0'].push(make_pair(make_pair(i, j), Move_Area[MAP[i][j] - '0']));
				Count_Area[MAP[i][j] - '0']++;
			}	// 이 Queue의 의미 = Idx번 플레이어의 성은 (i, j)에서 Move_Area[MAP[i][j])만큼 확장해 나갈 수 있습니다.
		}
	}
	memset(Flag, true, sizeof(Flag));
}

bool BFS(int Idx)
{
	bool Temp_Flag = false;
	queue<pair<pair<int, int>, int>> NQ = Q[Idx];
	while (NQ.empty() == 0)
	{
		int x = NQ.front().first.first;
		int y = NQ.front().first.second;
		int Cnt = NQ.front().second;
		NQ.pop();

		if (Cnt == Move_Area[Idx]) Q[Idx].pop();	// 원래 존재했던 성이라면, 새롭게 생긴 섬이 아니기 때문에 더이상 관리 X. 
		
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nCnt = Cnt;

			if (nCnt == 0) break;
			if (nx >= 0 && ny >= 0 && nx < N && ny < M)
			{
				if (MAP[nx][ny] == '.')
				{
					MAP[nx][ny] = Idx + '0';
					Count_Area[Idx]++;
					Q[Idx].push(make_pair(make_pair(nx, ny), Move_Area[Idx]));
					NQ.push(make_pair(make_pair(nx, ny), nCnt - 1));
					Temp_Flag = true;
				}
			}
		}
	}
	return Temp_Flag;
}

void Print()
{
	cout << "#################################################" << endl;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << MAP[i][j] << " ";
		}
		cout << endl;
	}
	cout << "#################################################" << endl;
}

bool Check()
{
	for (int i = 1; i <= P; i++)
	{
		if (Flag[i] == true) return true;
	}
	return false;
}

void Solution()
{
	while (1)
	{
		for (int i = 1; i <= P; i++)
		{
			if (Flag[i] == false) continue;
			bool Temp_Flag = BFS(i);
			if (Temp_Flag == false) Flag[i] = false;
		//	Print();
		}

		if (Check() == false) break;
	}

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

void Solve()
{
	Input();
	Solution();
}

int main(void)
{	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//freopen("Input.txt", "r", stdin);
	Solve();

	return 0;
}