알고리즘 문제
[백준] 3187번 양치기 꿍
feelcoding
2020. 2. 18. 23:14
728x90
https://www.acmicpc.net/problem/3187
3187번: 양치기 꿍
문제 양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다. 하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다. 꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<char>> arr(n, vector<char>(m));
vector<vector<bool>> visited(n, vector<bool>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == '#') visited[i][j] = true;
}
}
int surviveSheep = 0;
int surviveWolf = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j]) {
int wolf = 0;
int sheep = 0;
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (arr[cur.first][cur.second] == 'v') wolf++;
else if (arr[cur.first][cur.second] == 'k') sheep++;
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second]) {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.first + 1 < n && !visited[cur.first + 1][cur.second]) {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1]) {
q.push(make_pair(cur.first, cur.second - 1));
}
if (cur.second + 1 < m && !visited[cur.first][cur.second + 1]) {
q.push(make_pair(cur.first, cur.second + 1));
}
}
}
if (sheep > wolf) {
surviveSheep += sheep;
}
else {
surviveWolf += wolf;
}
}
}
}
cout << surviveSheep << " " << surviveWolf;
return 0;
}728x90