1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| import java.io.*;
import java.util.*;
class Main {
// 상하좌우를 탐색하기 위한 dx, dy 배열 선언
static int[] dx = new int[]{0, 1, 0, -1};
static int[] dy = new int[]{1, 0, -1, 0};
// N과 M을 전역변수로 선언
static int N;
static int M;
// 방문배열과 병사 배치도로 배열을 2차원 배열 선언
static boolean[][] visited;
static char[][] cloths;
// BFS 호출마다 쌓을 뭉쳐있는 병사 수를 구할 변수
static int cnt;
// W 병사 위력과 B 병사 위력을 담을 변수
static int w_sum;
static int b_sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 방문 배열 및 병사 배열 N*M 크기로 초기화
visited = new boolean[N][M];
cloths = new char[N][M];
// 입력 열대로 cloth 배열에 삽입
for(int i=0; i<M; i++) {
String str = br.readLine();
for(int j=0; j<str.length(); j++) {
cloths[j][i] = str.charAt(j);
}
}
// W 병사 위력 변수와 B 병사 위력 변수를 초기화
w_sum = 0;
b_sum = 0;
// 병사 배치가 저장된 cloth 배열을 순회하면서 BFS 호출
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
// 현재 좌표(위치가)가 방문하지 않은 위치일 경우 W, B 병사인지 확인하고 BFS 호출
if(!visited[i][j]) {
// 병사 위력을 연산할 cnt 변수를 1로 초기화
cnt = 1;
// 현재 위치가 W 병사라면 BFS 함수를 W를 포함하여 호출
// w_sum에 BFS 호출하여 구한 뭉친 병사의 수X2만큼 더해준다.
if(cloths[i][j] == 'W') {
BFS(i, j, 'W');
w_sum += cnt*cnt;
}
// 현재 위치가 B 병사라면 BFS 함수를 B를 포함하여 호출
// b_sum에 BFS 호출하여 구한 뭉친 병사의 수X2만큼 더해준다.
else {
BFS(i, j, 'B');
b_sum += cnt*cnt;
}
}
}
}
bw.write(w_sum + " " + b_sum + "\n");
bw.close();
br.close();
}
static void BFS(int x, int y, char sol) {
// 큐를 선언하고 호출시 받은 인자를 시작 노드로 삽입
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
// 해당 노드(위치)는 방문 처리
visited[x][y] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
// 해당 노드에서 상하좌우를 탐색한다.
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
// 탐색시 배열의 범위를 벗어나지 않아야 한다.
if(i>=0 && j>=0 && i<N && j<M) {
// 상하좌우로 탐색한 위치의 병사가 같은 병사인지 확인한다.
if(cloths[i][j] == sol && !visited[i][j]) {
cnt++;
visited[i][j] = true;
q.add(new int[]{i, j});
}
}
}
}
}
}
|
