[백준 1303] 전쟁-전투

문제 : 전쟁 - 전투

간단한 그래프 탐색 문제.

같은 문자들이 붙어있으면 DFS 한번으로 완전히 탐색할 수 있기 때문에 DFS로 구현하였다.

#include <iostream>

using namespace std;

int		n, m;
char		map[101][101];
int		visited[100][100];
int		w, b;
int		dx[4] = {1, -1, 0, 0};
int		dy[4] = {0, 0, 1, -1};
int		temp;

int		DFS(int y, int x, char s)
{
	int		i;
	int		nx, ny;
	int		ret;

	ret = 1;
	visited[y][x] = true;
	i = 0;
	while (i < 4)
	{
		nx = x + dx[i];
		ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m)
		{
			if (map[ny][nx] == s && !visited[ny][nx])
				ret += DFS(ny, nx, s);
		}
		i++;
	}
	return (ret);
}

int		main(void)
{
	int		i, j;
	
	scanf("%d %d", &n, &m);
	i = 0;
	while (i < m)
	{
		scanf("%s", map[i]);
		i++;
	}
	i = 0;
	while (i < m)
	{
		j = 0;
		while (j < n)
		{
			if (map[i][j] == 'W' && !visited[i][j])
			{
				temp = DFS(i, j, map[i][j]);
				w = w + (temp * temp);
			}
			else if (map[i][j] == 'B' && !visited[i][j])
			{
				temp = DFS(i, j, map[i][j]);
				b = b + (temp * temp);
			}
			j++;
		}
		i++;
	}
	printf("%d %d\n", w, b);
}