#1303 : 전쟁 - 전투

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.30

첫 칸부터 마지막 칸까지 훑으면서,

아직 방문하지 않은 칸에 대하여 그 칸을 시작점으로 그 칸과 같은 편인 칸에 대하여 dfs를 돈다. 그러면서 몇 칸을 방문했는지 센다.

해당 dfs가 끝나면 몇 칸 방문했는지 센 수를 제곱하여 정답에 더한다.

 

코드

Java(2022.05.30)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static boolean[][] map;	//전쟁터 지도
	static boolean[][] visited;	//방문여부 저장용 배열
	static int cnt;	//해당 구역의 동일한 편 병사의 수
	static int n, m;	//전쟁터의 가로 크기, 세로 크기
	//아래는 상하좌우 재귀 시에 사용할 좌표변경용 배열
	static int[] r = {-1, 1, 0, 0};
	static int[] c = {0, 0, -1, 1};
	
	static void dfs(int row, int col, boolean color) {
		//전쟁터 바깥이거나, 이미 방문했거나, 상대편이면 return
		if(row<0 || col<0 || row>=m || col>=n)return;
		if(visited[row][col])return;
		if(map[row][col] != color)return;
		
		visited[row][col] = true;	//방문했다고 표시
		cnt++;	//인접한 같은 편 수 세기
		for(int i=0; i<4; i++)dfs(row+r[i], col+c[i], color);	//상하좌우에 대하여 재귀
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new boolean[m][n];
		visited = new boolean[m][n];
		//전쟁터 읽어오기
		for(int i = 0; i<m; i++) {
			String input = br.readLine();
			for(int j = 0; j<n; j++) {
				if(input.charAt(j)=='B') map[i][j]=true;
			}
		}
		//깊이우선탐색 하기
		int white = 0;
		int blue = 0;
		for(int i = 0; i<m; i++) {
			for(int j = 0; j<n; j++) {
				if(!visited[i][j]) {	//아직 방문하지 않은 칸에 대하여
					cnt = 0;	//인접한 같은 편 수를 셀 변수를 0으로 초기화
					dfs(i, j, map[i][j]);	//깊이우선탐색 수행
					if(map[i][j]) blue += Math.pow(cnt, 2);	//센 값을 제곱해서 알맞은 팀에 더해줌
					else white += Math.pow(cnt, 2);
				}
			}
		}
		//정답 출력
		System.out.print(white + " " + blue);
	}

}