#1303 전쟁 - 전투 (DFS)

이번 문제는 Silver I 문제로 기초적인 DFS 문제입니다.

 

핵심은 연결된 지역의 수를 알아내는 것으로, "섬의 개수" 등과 같은 문제와 동일합니다.

MxN 지역(보통은 NxM인데, 여기서는 MxN입니다.)에 W로 마킹된 곳과 B로 마킹된 곳이 있습니다.  대각선으로는 이어질 수 없고, 상하좌우로만 이어집니다.  서로 이어진 곳을 하나의 집단이라고 한다면, 그 집단의 구성수의 제곱을 합한 것이 전투력이 됩니다.  이 전투력을 각각의 집단 'W'와 'B'를 표시하면 됩니다.

 

DFS

 

DFS로 해결해도 되고, BFS로 해결해도 되는 문제입니다.  저는 개인적으로 DFS를 선호합니다.  결국 큐 자료구조를 선호하느냐 아니면 스택자료 구조를 선호하느냐의 차이겠죠.  또한 경계선 검사를 할 때, 미리 더 넓은 지역을 잡아놓고 새로운 위치에서 경계를 벗어났을 때, 동일한 방식으로 검사하는 방법이 있고, 위치의 좌표값으로 경계선을 검사하는 방법이 있습니다.  후자를 보통 쓰는데, 이 문제는 전자를 이용해서 사용해보았습니다.  경계선 확장은 다음과 같이 할 수 있습니다.  여기서는 'W', 'B' 로 유효지역은 채워져있으므로 그 외의 지역을 0으로 채우면, 위치값을 따라 DFS로 연결해나가는 문제는 간단하게 해결됩니다.  경계선 확장을 하려면 2행과 2열을 추가해주어야 합니다.  그리고 유효영역 이외의 지역을 미리 클리어해주어야 합니다.  4x4 영역에 데이터가 있는 것이라면 경계선 확장을 하였을 때의 맵은 다음과 같습니다.

 

	W	W	W	B
	W	B	W	B
	W	W	W	B
	B	B	B	B

 

위와 같이 유효영역 4x4 밖에는 'W', 'B'가 아닌 다른 값으로 채워주면 됩니다.  제 경우에는 가장 보편적인 값인 0을 사용했습니다.

 

DFS와 경계선 확장을 해서 푼 제 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1303 - War - Fight
//    - by Aubrey Choi
//    - created at 2020-01-19
//--------------------------------------------------------------------
#include <stdio.h>

char z[102][104]; int n, m;
int dfs(int y,int x,int c)
{
  int r=1, d[][2]={0,1, 1,0, 0,-1, -1,0}, i;
  z[y][x]=0; 
  for(i=0;i<4;i++)
  {
    int ny=y+d[i][0], nx=x+d[i][1];
    if(z[ny][nx]!=c) continue;
    r+=dfs(ny,nx,c);
  }
  return r;
}
int main()
{
  int i, j, r1=0, r2=0, s;
  scanf("%d%d",&m,&n);
  for(i=1;i<=n;i++) scanf("%s",z[i]+1);
  for(i=1;i<=n;i++) for(j=1;j<=m;j++)
  {
    if(z[i][j]=='W') { s=dfs(i,j,'W'); r1+=s*s; }
    else if(z[i][j]=='B') { s=dfs(i,j,'B'); r2+=s*s; }
  }
  printf("%d %d\n", r1, r2);
}