백준 1303 전쟁 - 전투 (Java)

1. 문제 링크

1303번: 전쟁 - 전투

 

2. 문제 및 입출력예제

 

3. 문제 풀이

입력이 W와 B 2개로 구성되어 있어서 boolean 배열로 만들었다.

아군의 경우와 적군의 경우를 별도로 탐색했다.

아군인 경우에는 true이면서 방문하지 않은 곳을 탐색 시작으로 한다.

bfs에서는 사방 탐색을 진행하는데 범위 안에 있으면서 방문하지 않은 곳을 탐색한다.

큐에서 꺼낸 수만큼이 연결되어 있는 것으로 그 수를 반환한다.

sum에 그 수의 제곱만큼씩 더해 위력의 합을 구한다.

 

+) 가로 세로가 반대로 평소와는 다른 순서로 주어지기 때문에 주의해야 한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int N, M;
	static boolean[][] map, visit;
	static int[] dx = {0,0,-1,1}, dy = {-1,1,0,0};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		M = Integer.parseInt(split[0]);
		N = Integer.parseInt(split[1]);
		
		map = new boolean[N][M];
		visit = new boolean[N][M];
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				map[i][j] = str.charAt(j) == 'W' ? true: false;
			}
		} 
        
		//true로 한 번 false로 한 번
		int sumT = 0, sumF = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] && !visit[i][j]) {
					sumT+= Math.pow(bfs(i, j), 2);
				}
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(!map[i][j] && !visit[i][j]) {
					sumF += Math.pow(bfs(i, j), 2);
				}
			}
		}
		System.out.println(sumT +" "+sumF);
	}
	
	private static int bfs(int i, int j) {
		int num = 0;
		Queue<int[]> queue = new ArrayDeque<>(); 
		queue.offer(new int[] {i, j});
		visit[i][j] = true;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			num++;
			int x = now[0];
			int y = now[1];
			for(int d=0;d<4;d++) {
				int X = x+dx[d];
				int Y = y+dy[d];
				
				if(X<0 || X>=N || Y<0 || Y>=M || map[i][j]!=map[X][Y] ||visit[X][Y]) {
					continue;
				}
				queue.offer(new int[] {X, Y});
				visit[X][Y] = true;
			}
		}
		return num;
	}
}