[백준] 1303 전쟁 - 전투 - BFS(너비우선탐색) JAVA

https://www.acmicpc.net/problem/1303

코드설명

BFS(너비우선탐색) 을 활용합니다.

 

전형적인 BFS 문제로써, 구현에 어려움은  없습니다.

유의할점은, 모든 N을 구한뒤 제곱값을 구하는것이 아닌 각 그룹마다 제곱값을 구해서 더해야합니다.

if(arr[i][j] == 'W' && visited[i][j] == false) {
    temp = BFS(i, j, 'W');
    powerW += temp * temp;
}else if(arr[i][j] == 'B' && visited[i][j] == false){
    temp = BFS(i, j, 'B');
    powerB += temp * temp;
}

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static char[][] arr = new char[101][101];
	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());
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = st.nextToken().toCharArray();
		}
		
		for(int i=0;i<M; i++) {
			for(int j=0;j<N;j++) {
				int temp = 0;
				if(arr[i][j] == 'W' && visited[i][j] == false) {
					temp = BFS(i, j, 'W');
					powerW += temp * temp;
				}else if(arr[i][j] == 'B' && visited[i][j] == false){
					temp = BFS(i, j, 'B');
					powerB += temp * temp;
				}
			}
		}
		
		System.out.println(powerW  + " " +powerB);
		
	}
	static int powerW= 0, powerB = 0;
	static boolean[][] visited = new boolean[101][101];
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int BFS(int r, int c, char type) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {r, c});
		visited[r][c] =true;
		int cnt = 1;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for(int dir = 0; dir < 4; dir++) {
				int nr = temp[0] + dx[dir];
				int nc = temp[1] + dy[dir];
				if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
				if(visited[nr][nc] == true) continue;
				if(arr[nr][nc] != type) continue;
				
				visited[nr][nc] = true;
				cnt += 1;
				q.offer(new int[] {nr, nc});
			}
		}
		
		return cnt;
	}
}