백준 3184 - 양(C++)

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

3184번: 양

BFS를 이용한 간단한 문제입니다.

 

 

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

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

using namespace std;

char Map[251][251];
bool check[251][251];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int R, C;
int number_W, number_S;

void bfs(int X, int Y, int s, int w) {
	queue<pair<int, int>> q;
	q.push({ X,Y });
	int S = s, W = w;
	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 <= R && yy >= 1 && yy <= C) {
				if (Map[xx][yy] != '#' && !check[xx][yy]) {
					if (Map[xx][yy] == 'o') S++;
					else if (Map[xx][yy] == 'v') W++;
					check[xx][yy] = true;
					q.push({ xx,yy });
				}
			}
		}
	}
	if (S > W) number_W -= W;
	else number_S -= S;
}

void solve() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (Map[i][j] != '#' && !check[i][j]) {
				check[i][j] = true;
				if (Map[i][j] == 'o') bfs(i, j, 1, 0);
				else if (Map[i][j] == 'v') bfs(i, j, 0, 1);
				else bfs(i, j, 0, 0);
			}
		}
	}
	cout << number_S << " " << number_W;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 'v') number_W++;
			else if (Map[i][j] == 'o') number_S++;
		}
	}
	solve();
	return 0;
}

 

 

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