[백준] 1303 전쟁 - 전투 C++

🥈 Silver 1 전쟁 - 전투 문제풀이

문제설명

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

---

C++ 풀이

#include <iostream>
#include <queue>
#include <string>

using namespace std;

char board[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


// char c를 받아서
// c와 동일한 문자들을 확인함
int bfs(int n, int m, char c)
{
	bool visited[101][101] = {false, };
	queue<pair<int, int> > Q;
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == c && visited[i][j] == false)
			{
				int count = 0;
				Q.push(make_pair(i, j));
				visited[i][j] = true;
				while (!Q.empty())
				{
					auto cur = Q.front();
					Q.pop();
					count++;
					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m)
							continue;
						if (visited[nx][ny] || board[nx][ny] != c)
							continue;
						Q.push(make_pair(nx, ny));
						visited[nx][ny] = true;
					}
				}
				sum += (count * count);
			}
		}
	}
	return sum;
}

int main()
{
	int n, m, alias, enemy;
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			board[i][j] = s[j];
		}
	}
	alias = bfs(n, m, 'W');
	enemy = bfs(n, m, 'B');
	cout << alias << ' ' << enemy;
}

---

추가 설명

기본적으로 N x M 배열에 'W' 아니면 'B' 로 모든 칸이 차 있다.
뭉쳐있는 병사 N명은 N^2의 위력을 낼 수 있기에, 뭉쳐있는 병사들을 탐색한 다음, 제곱하여 위력에 더하여 주는 것을 반복해야 한다.
탐색은 기본적으로 BFS로 진행이 되며 bfs 함수는 파라미터로 받은 문자를 지도에서 세어 위력을 계산해주도록 작성하였다.