[백준 1303] 전쟁 - 전투

문제 설명

문제 링크

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.
그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다.
과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

다음과 같은 입력이 주어졌을 때,

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

다음과 같이 출력되도록 하면된다. (주어진 입력으로부터 각 팀의 위력을 출력하는 것이다. 이 때, N명이 뭉쳐있다면 N^2의 위력을 낸다.)

130 65

생각 정리

탐색을 하며, 우리 팀과 상대팀에 대해 서로 몇명이 인접해있는지 구해서 제곱하고 각각 더해간다.

//첫째줄에는 전쟁터의 가로크기와 새로크기가 나온다
        //이중 for문을 돌리면서 해당 위치에서 방문하지 않았고 
            //W라면 bfs를 돌려서 크기를 구해서 Wpower에 더해준다.
            //B라면 bfs를 돌려서 크기를 구해서 Bpower에 더해준다.

정리된 생각에 대한 논리

코드를 정리하고 실행했을 때 틀린 답이 나왔다.
그 이유는 bfs함수를 돌릴 때, 방문 여부만 판별하고 우리팀(W)인지 상대팀(B)인지 판별해주지 않았다.

완성

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

public class BOJ1303 {
    static boolean[][] visited;
    static char[][] war;
    static int wpower = 0, bpower=0;
    static int N,M;
    static int[] dx = {-1, 0, 1, 0}; //상우하좌
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[M][N];
        war = new char[M][N];

        for(int i=0; i<M; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                war[i][j] = str.charAt(j);
            }
        }

        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(visited[i][j] != true && war[i][j] == 'W'){
                    visited[i][j] = true;
                    bfs(i, j, 'W');
                }
                if(visited[i][j] != true && war[i][j] == 'B'){
                    visited[i][j] = true;
                    bfs(i, j, 'B');
                }
            }
        }

        System.out.println(wpower + " " + bpower);


    }

    static void bfs(int x, int y, char team) {
        Queue<Position> queue = new LinkedList<>();
        int cnt = 0;
        queue.add(new Position(x, y));

        while(!queue.isEmpty()) {
            Position p = queue.poll();
            cnt++;

            for(int i=0; i<4; i++) {
                int nextX = p.x + dx[i];
                int nextY = p.y + dy[i];

                if(nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) continue;
                else if(visited[nextX][nextY]) continue;
                else {
                    if(team == 'W' && war[nextX][nextY] == 'B') continue;
                    else if(team == 'B' && war[nextX][nextY] == 'W') continue;
                    else {
                        visited[nextX][nextY] = true;
                        queue.add(new Position(nextX, nextY));
                    }   

                }

                
            }
        }

        if(team == 'W')
            wpower += Math.pow(cnt, 2);
        else if(team == 'B')
            bpower += Math.pow(cnt, 2);
    }
    
}