[백준] 1303 전쟁 - 전투

문제

---

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

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

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

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

 

 

 

 

 

 

풀이

---

간단하게 BFS 를 이용하여 B 와 W 이어진 의 갯수를 세는 방식으로 풀었다.

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int maxr, maxc;
	static String[][] map;
	static boolean[][] visited;
	static int[][] move = {{1,0}, {-1,0}, {0,1}, {0,-1}};
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		maxc = Integer.parseInt(st.nextToken());
		maxr = Integer.parseInt(st.nextToken());
		map = new String[maxr][maxc];
		visited = new boolean[maxr][maxc];
		
		for(int i = 0 ; i < maxr ; i++) {
			String[] split = bufferedReader.readLine().split("");
			
			for(int j = 0 ; j < maxc ; j++) {
				map[i][j] = split[j];
			}
		}
		
		int sumWhite = 0;
		int sumBlue = 0;
		for(int i = 0 ; i < maxr; i++) {
			for(int j = 0 ; j < maxc ; j++) {
				if(map[i][j].equals("W") && !visited[i][j]) {
					sumWhite += Math.pow(getCount(i, j, map[i][j]),2);
				}
				
				else if(map[i][j].contentEquals("B") && !visited[i][j]) {
					sumBlue += Math.pow(getCount(i, j, map[i][j]), 2);
				}
			}
		}
		
		sb.append(sumWhite + " " + sumBlue);
		System.out.println(sb);
	}
	
	static class Point{
		int r, c;
		
		Point(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static int getCount(int r, int c, String color) {
		
		int cnt = 0;
		
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(r, c));
		visited[r][c] = true;
		
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			
			cnt++;			
			for(int i = 0 ; i < 4 ; i++){
				int nr = now.r + move[i][0];
				int nc = now.c + move[i][1];

				if(nr < 0 || nr >= maxr || nc < 0 || nc >= maxc) { continue; }
				if(visited[nr][nc] || !map[nr][nc].equals(color)) { continue; }
				
				visited[nr][nc] = true;
				queue.add(new Point(nr, nc));
			}
		}

		return cnt;	
	}
	
	
}