풀이
맵에서 울타리 '#'가 아닌 지역을 시작점으로 탐색을 해서 양과 늑대의 수를 체크한다.
이때 양의 수가 늑대의 수보다 많다면 양이 싸움에서 이기는 것이고,
양의 수가 늑대의 수보다 작거나 같다면 양이 싸움에서 지는 것으로 구현하면 된다.
#include <iostream>
#include <queue>
using namespace std;
int r, c, wolf, sheep;
char field[251][251];
bool vis[251][251];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
void findSheepAndWolf(int x, int y)
{
int w = 0, s = 0;
queue<pair<int, int >> q;
q.push({ x,y });
vis[x][y] = true;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
if (field[x][y] == 'v') w++;
if (field[x][y] == 'k') s++;
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (field[nx][ny] != '#' && !vis[nx][ny])
{
vis[nx][ny] = true;
q.push({ nx,ny });
}
}
}
if (s > w)
sheep += s;
else
wolf += w;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> r >> c;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
cin >> field[i][j];
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
if (field[i][j] != '#' && !vis[i][j])
{
findSheepAndWolf(i, j);
}
}
}
cout << sheep << ' ' << wolf << '\n';
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 10799] 쇠막대기 (C++) (0) | 2021.04.08 |
---|---|
[백준 1874] 스택 수열 (C++) (0) | 2021.04.08 |
[백준 2178] 미로 탐색 (0) | 2021.04.05 |
[백준 2606] 바이러스 (0) | 2021.04.05 |
[백준 16956] 늑대와 양 (0) | 2021.04.05 |