Algorithm/BFS & DFS
[백준] 1303번 : 전쟁 (C++)
루시킴
2021. 8. 25. 14:45
https://www.acmicpc.net/problem/1303
1303번: 전쟁 - 전투
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는
www.acmicpc.net
자주 나오는 유형으로, DFS를 이용하여 간단히 구현하였다. 설명은 생략 :)
#include <iostream>
using namespace std;
int N, M,W,B;
char map[100][100];
int visit[100][100];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int tmp;
void solve(int x, int y) {
if (visit[x][y]) return;
tmp++;
visit[x][y] = 1;
for (int i = 0; i < 4; i++) {
int cx = x + dx[i];
int cy = y + dy[i];
if (cx >= 0 && cx < M && cy >= 0 && cy < N && !visit[cx][cy] && map[cx][cy] == map[x][y]) {
solve(cx, cy);
}
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
tmp = 0;
solve(i, j);
if (map[i][j] == 'W') W += tmp * tmp;
else B += tmp * tmp;
}
}
}
cout << W << " " << B << endl;
}