[BOJ] 전쟁-전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고,

적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

풀이

탐색문제이다.
맵에 주어진 문자에 따라서 탐색해야 할 조건이 달라지는 문제이다.
따라서 "W"일때와 "B"일때 각각 한번씩 BFS를 진행하여 갯수를 세어
조건에 맞게 제곱해주면 된다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static String[][]map;
    static boolean[][]visited;
    static int N;
    static int M;
    static int[] x_loc = {1, -1, 0, 0};
    static int[] y_loc = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        M = Integer.parseInt(str[0]);
        N = Integer.parseInt(str[1]);
        visited = new boolean[N][M];
        map = new String[N][M];

        for(int i = 0; i < N; i++) {
            str = br.readLine().split("");
            for(int j = 0; j < M; j++) {
                map[i][j] = str[j];
            }
        }

        int wSum = 0;
        for(int i = 0; i < N; i++) {
            int count = 0;
            for(int j = 0; j < M; j++) {
                if (!visited[i][j] && map[i][j].equals("W")) {
                    count += Math.pow(bfs(i, j, "W"), 2);
                }
            }
            wSum += count;
        }

        visited = new boolean[N][M];
        int bSum = 0;
        for(int i = 0; i < N; i++) {
            int count = 0;
            for(int j = 0; j < M; j++) {
                if (!visited[i][j] && map[i][j].equals("B")) {
                    count += Math.pow(bfs(i, j, "B"), 2);
                }
            }
            bSum += count;
        }

        System.out.print(wSum + " " + bSum);
    }

    static int bfs(int startX, int startY, String mark) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(startX, startY));
        visited[startX][startY] = true;
        int count = 1;

        while(!queue.isEmpty()) {
            Location loc = queue.poll();

            for(int i = 0; i < 4; i++) {
                int x = loc.x + x_loc[i];
                int y = loc.y + y_loc[i];

                if (check(x, y) && !visited[x][y] && map[x][y].equals(mark)) {
                    visited[x][y] = true;
                    count++;
                    queue.add(new Location(x, y));
                }
            }
        }

        return count;
    }

    static boolean check(int x, int y) {
        return (x >= 0 && x < N) && (y >= 0 && y < M);
    }

    static class Location {
        int x;
        int y;

        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%A0%84%EC%9F%81-%EC%A0%84%ED%88%AC