※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
대표적인 깊이 우선 탐색(DFS) 문제입니다.
뭉쳐있는 경우, 즉 '동서남북' 으로 자신과 같은 옷의 병사가 뭉쳐 있을 경우를 찾아야 합니다.
탐색을 하기 위해 재귀 함수를 작성합니다.
이 때, 한 번 방문했던 지점을 다시 방문하게 될 경우 재귀가 무한정 들어가게 되어 stack overflow가 발생합니다.
그러므로 방문을 체크하는 boolean 배열을 선언한 후, 방문한 지점을 체크하도록 하면 됩니다.
원리만 이해한다면 풀기는 쉬운 문제입니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s[101];
bool visited[101][101];
int w,h,cnt[26], ans[26];
void dfs(int x, int y, char c)
{
visited[x][y] = true;
cnt[c - 'A']++;
if (x > 0 && !visited[x - 1][y] && s[x - 1][y] == c) dfs(x - 1, y, c);
if (y > 0 && !visited[x][y - 1] && s[x][y - 1] == c) dfs(x, y - 1, c);
if (x + 1 < h && !visited[x + 1][y] && s[x + 1][y] == c) dfs(x + 1, y, c);
if (y + 1 < w && !visited[x][y + 1] && s[x][y + 1] == c) dfs(x, y + 1, c);
}
int main()
{
ios::sync_with_stdio(false);
cin >> w >> h;
for (int i = 0; i < h; i++) cin >> s[i];
for(int i=0; i<h; i++)
for (int j = 0; j < w; j++)
{
if (!visited[i][j])
{
int q = s[i][j] - 'A';
dfs(i, j, s[i][j]);
ans[q] += cnt[q]* cnt[q];
cnt[q] = 0;
}
}
cout << ans[22] << " " << ans[1];
}