[BOJ/C++] 1303(전쟁 - 전투)

1. Link

https://www.acmicpc.net/problem/1303

2. 풀이 과정

1. 같은 팀의 병사들은 모이면 모일수록 강해짐, 대각선으로는 인정 X -> BFS

• 2중 for문으로 탐색을 통해 각 팀의 값을 합산해주는 것으로 결과를 구할 수 있습니다.

1. 2중 for문을 돌며 방문했는지 여부를 확인 후 방문하지 않았으면 해당 위치에서 BFS를 시작합니다.

2. 시작한 위치에서 BFS를 돌며 처음 위치의 값과 동일한 알파벳(값)이면 지속적으로 탐색하고, 이미 방문했거나 다른 알파벳이면 생략합니다.

3. 각 BFS를 탐색한 후 나온 값(N^2)을 최댓값과 비교하여 결과를 바꿔줍니다.

3. 정답 코드

#include <iostream>
#include <queue>
using namespace std;
#define p pair<int, int>

int n, m, white = 0, blue = 0;
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };
char a[101][101];
bool vis[101][101]{ 0 };

void input() {
	cin >> n >> m;
	string s;
	for (int i = 1; i <= m; ++i) {
		cin >> s;
		for (int j = 1; j <= n; ++j) {
			a[i][j] = s[j - 1];
		}
	}
}

void bfs(int x, int y) {
	queue<p> q;
	q.push({ x,y });
	vis[x][y] = 1;
	int cnt = 0;
	while (!q.empty()) {
		p cur = q.front(); q.pop();
		++cnt;
		for (int dir = 0; dir < 4; ++dir) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 1 || ny < 1 || nx > m || ny > n) continue;
			if (vis[nx][ny] || a[x][y] != a[nx][ny]) continue;
			vis[nx][ny] = 1;
			q.push({ nx,ny });
		}
	}
	if (a[x][y] == 'W') {
		white += cnt * cnt;
	}
	else {
		blue += cnt * cnt;
	}
}

void solution() {
	input();
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (vis[i][j]) continue;
			bfs(i, j);
		}
	}
	cout << white << ' ' << blue;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}