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

문제 링크

1303번: 전쟁 - 전투

문제 요약

전쟁을 하는데, (서로 인접해 있는 병사들의 수)$^2$만큼 위력을 낼 수 있다. 이 때, 각 국가의 위력을 구해야 한다.

접근 방법

단순 그래프 탐색 문제입니다. 방문하지 않은 정점에서 시작해서 몇 개의 정점까지 방문이 가능한지 세고, 제곱해서 각 국가에 더해주면 됩니다. N이 열이고 M이 행이라는 점 때문에 문제를 꼼꼼히 읽어야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m, team1 = 0, team2 = 0, dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
char b[101][101];
bool visited[101][101];

void bfs(int r, int c, char team)
{
	queue<pair<int, int>> q;
	q.push({ r, c });
	visited[r][c] = true;

	int cnt = 0;
	while (!q.empty())
	{
		pair<int, int> now = q.front();
		q.pop();
		cnt++;

		for (int i = 0; i < 4; i++)
		{
			int nr = now.first + dir[i][0], nc = now.second + dir[i][1];
			if (nr >= 1 && nr <= m && nc >= 1 && nc <= n && !visited[nr][nc] && b[nr][nc] == team)
			{
				visited[nr][nc] = true;
				q.push({ nr, nc });
			}
		}
	}

	if (team == 'W')
		team1 += cnt * cnt;
	else
		team2 += cnt * cnt;
}

int main(void)
{
	cin >> n >> m;

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> b[i][j];

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			if (!visited[i][j])
				bfs(i, j, b[i][j]);

	cout << team1 << ' ' << team2;
	return 0;
}