[Silver I] 전쟁 - 전투 - 1303 (JAVA)

 

문제 요약

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

---

문제 분석

맵을 받아서 순차적으로 탐색하며 BFS를 돌린다. 이때 찾은 병사들의 색을 기준으로 값을 갱신해준다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static char[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        boolean[][] v = new boolean[N][M];
        for(int i = 0; i < N; i++){
            arr[i] = br.readLine().toCharArray();
        }
//        for(char[] a : arr){
//            System.out.println(Arrays.toString(a));
//        }
        int wScore = 0, bScore = 0;
        for(int r = 0; r < N; r++){
            for(int c = 0; c < M; c++){
                if(v[r][c] != true){
                    v[r][c] = true;
                    int score = bfs(r, c, arr, v);
                    if(arr[r][c] == 'W'){
                        wScore += Math.pow(score, 2);
                    }
                    else{
                        bScore += Math.pow(score, 2);
                    }
                }
            }
        }
        System.out.println(wScore + " " + bScore);
    }
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    private static int bfs(int R, int C, char[][] arr, boolean[][] v) {
        int score = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{R,C});
        char baseLetter = arr[R][C];
        while(!q.isEmpty()){
            int[] curr = q.poll();
            for(int d = 0; d < 4; d++){
                int nr = curr[0] + dr[d];
                int nc = curr[1] + dc[d];
                if(isArrOut(nr,nc) || v[nr][nc] || arr[nr][nc] != baseLetter){
                    continue;
                }
                v[nr][nc] = true;
                score++;
                q.add(new int[]{nr,nc});
            }
        }
        return score;
    }
    private static boolean isArrOut(int r, int c){
        return r < 0 || c < 0 || r >= N || c >= M;
    }
}

---

---