[BOJ] 3184. 양

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

3184번: 양

마당에 영역별로 양과 늑대가 있는데, 같은 영역 안에서 양이 늑대보다 더 많으면 싸워서 이길 수 있다.

마지막에 살아남은 양과 늑대의 수를 출력하는 문제이다.

 

먼저 각 영역에서의 양의 수와 늑대의 수를 구하기 위해서 bfs를 이용했다. bfs를 통해 연결된 영역을 구하면서

양이나 늑대가 있는 경우에 숫자를 카운트한다.

 

한 영역의 탐색이 끝난 후에 양의 수와 늑대의 수를 비교해준다.

양의 수가 많은 경우 전체 양의 수에 해당 영역의 양의 수를 더해준다.

그렇지 않은 경우 늑대의 수를 전체 늑대의 수에 더해주면 된다.

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
 
int r, c, sheep, wolf;
bool check[250][250];
char map[250][250];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int ocnt = 0;
    int vcnt = 0;
 
    //출발점이 양이나 늑대인 경우
    if (map[x][y] == 'o') {
        ocnt++;
    }
    else if (map[x][y] == 'v') {
        vcnt++;
    }
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            //범위체크
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            
            //방문체크
            if (check[nx][ny]) continue;
 
            //울타리
            if (map[nx][ny] == '#') continue;
            
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
 
            //이동하는 곳에 양이 있는 경우 양의 수 증가
            if (map[nx][ny] == 'o') {
                ocnt++;
            }//이동하는 곳에 늑대가 있는 경우 늑대의 수 증가
            else if (map[nx][ny] == 'v') {
                vcnt++;
            }
        }
    }
 
 
    //탐색이 끝난 후에 양의 수가 더 많으면 양의 수를 전체 양의 수에 더한다.(양이 살아 남음)
    if (ocnt > vcnt) {
        sheep += ocnt;
    }
    else {//늑대의 수가 더 많거나 같은 경우 늑대가 살아남는다.
        wolf += vcnt;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
        }
    }
 
 
 
    //영역별로 bfs를 실행
    //방문한 곳(다른 영역)이나 울타리는 탐색하지 않는다.
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (map[i][j] == '#') continue;
            if (check[i][j]) continue;
            bfs(i, j);
        }
    }
 
 
    cout << sheep << ' ' << wolf;
    
    return 0;
}