백준 1303- 전쟁 - 전투(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

BFS or DFS를 이용해 푸는 문제입니다.

BFS를 통해 W 혹은 B가 뭉쳐있는 수를 구한 뒤, 전체의 합에 더해주면 되는 문제입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int N, M;
int check[101][101];
char map[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


int bfs(int X, int Y, char knight) {
	queue<pair<int, int>> q;
	q.push({ X,Y });
	check[X][Y] = 1;
	int cnt = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (check[xx][yy] == 0 && map[xx][yy] == knight) {
					check[xx][yy] = 1;
					cnt++;
					q.push({ xx,yy });
				}
			}
		}
	}
	return cnt * cnt;
}

void solve() {
	int sum_W = 0, sum_B = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] == 'W') {
				if (check[i][j] == 0) sum_W += bfs(i, j, map[i][j]);
			}
			else {
				if (check[i][j] == 0) sum_B += bfs(i, j, map[i][j]);
			}
		}
	}
	cout << sum_W << " " << sum_B;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> M >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요