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

# 전쟁 - 전투(1303)

## 문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

## 입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

## 출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

## 예제 입력 1

```java
5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW
```

## 예제 출력 1

```java
130 65
```

## 풀이

이번 문제는 bfs의 진행을 구체적으로 다시 생각해볼 수 있는 문제였다.

때문에 프린트를 해가며 각각 bfs의 진행을 눈으로 확인하며 해결했다.

```java
import java.util.*;
import java.io.*;

public class Main{
static int n, m, bsum, wsum, bcnt= 0, wcnt= 0;
    static boolean[][] visited;
    static int[][] arr;
    static int[] dx={1, 0, -1, 0};
    static int[] dy={0, 1, 0, -1};
    static Queue<int[]> q= new LinkedList<>();

    public static void main(String[]args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n= Integer.parseInt(st.nextToken());
        m= Integer.parseInt(st.nextToken());
        arr= new int[m][n];
        visited= new boolean[m][n];

        for(int i = 0; i <m; i++) {
            String str = br.readLine();
            for(int j = 0; j <n; j++) {
                if(str.charAt(j)== 'B') {
                    arr[i][j]= 1;
                }else
                    arr[i][j]= 0;
            }
        }

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j]==1 && !visited[i][j]){
                    bcnt++;
                    fn(i, j, 'B');
                    bsum+=Math.pow(bcnt, 2);
                    bcnt=0;
                }
            }
        }    

//초기화
q= new LinkedList<>();
        for(int i = 0; i <m; i++) {
for(int j = 0; j <n; j++) {
visited[i][j]= false;
}
}

for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(arr[i][j]==0 && !visited[i][j]){
wcnt++;
fn(i, j, 'W');
wsum+=Math.pow(wcnt, 2);
wcnt=0;
}
}
}

System.out.println(wsum+ " " +bsum);
}

public static void fn(int x, int y, char c) {
q.add(new int[]{x, y});
visited[x][y]= true;
        while(!q.isEmpty()) {
int[]xy =q.poll();

            for(int i = 0; i < 4; i++) {
int nx = xy[0]+dx[i];
                int ny = xy[1]+dy[i];
//값이 넘어가거나 이미 체크했다면 넘어가고
if(nx < 0 || nx >=m|| ny < 0 || ny >=n||visited[nx][ny])
continue;
//B를 찾는 경우 : B를 1로 체크했기 떄문에 0이면 지나가고
if(c == 'B' &&arr[nx][ny]== 0)
continue;
//W를 찾는 경우 : W는 0으로 체크했기 때문에 1이면 지나가고
if(c == 'W' &&arr[nx][ny]== 1)
continue;

//조건에 걸리지않았다면 체크하고
visited[nx][ny]= true;
//큐에 집어넣고
q.add(new int[]{nx, ny});
//여기부분이 다음 인덱스로 넘어가면서 진행되는 부분이고
if(c == 'B') {
bcnt++;
}else{
wcnt++;
}
}
//여기부분이 하나의 점에서 다움직이면 넘어가는 곳
//            System.out.println("bcnt : " + bcnt);
}

}
}
```
