C++ / 백준 / 3184 / 양

문제

https://www.acmicpc.net/problem/3184

3184번: 양

문제풀이

DFS로 풀었다.

visit함수를 따로 만들지 않고 방문을 했으면 #표시를 했다.

울타리 안에서 상하좌우 어디로든 갈 수 있다.

전역 변수로 양 o, 늑대 v를 만들어서 메인 문에서 o과 v를 초기화하고 DFS함수를 실행한다.

메인 문에서 DFS는 #를 제외한., v, o일 때만 실행한다.

근처에 가지 않은 곳은 울타리밖에 없어 더 이상 갈 수 없을 때 메인 문으로 돌아온다.

그때 양과 늑대의 수를 비교해서 양이 더 많을 경우 양의 수만 answer.first에 더하고 그 외에는 answer.second에 늑대의 수만 더한다.

모든 DFS문이 끝나면 양과 늑대의 수를 출력한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<char>>yard;
vector<vector<int>>loc = { {-1,0},{1,0},{0,-1},{0,1} };

int o, v;
int R, C;

void DFS(int y, int x) {
	if (yard[y][x] == 'o') o++;
	else if (yard[y][x] == 'v') v++;
	yard[y][x] = '#';
	for (int idx = 0; idx < 4; ++idx) {
		int n_y = y + loc[idx][0];
		int n_x = x + loc[idx][1];
		if (n_y >= 0 && n_y < R && n_x >= 0 && n_x < C)
			if (yard[n_y][n_x] != '#')
				DFS(n_y, n_x);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> R >> C;
	yard = vector<vector<char>>(R, vector<char>(C, ' '));
	int y = 0, x = 0;
	for (y = 0; y < R; ++y)
		for (x = 0; x < C; ++x)
			cin >> yard[y][x];

	pair<int, int>answer;

	for (y = 0; y < R; ++y) {
		for (x = 0; x < C; ++x) {
			o = 0, v = 0;
			if (yard[y][x] != '#') {
				DFS(y, x);
				if (o > v) answer.first += o;
				else answer.second += v;
			}
		}
	}
	cout << answer.first << " " << answer.second;
}