전쟁 - 전투(1303)

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

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1

130 65

풀이

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

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

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);
}

}
}