3184번-양

문제

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

3184번: 양

---

접근방법

1) 접근 사고

1. 울타리가 아닌 영역을 탐색한다.

2. 울타리가 아닌 영역의 양과 늑대수를 측정한다.

3. 양이 늑대수보다 클 경우에는 양의 결과를 반환하는 변수에 양의 수를 더해주고 아닌 경우에는 늑대의 결과를 반환하는 변수에 늑대의 수를 더해준다.

 

2) 시간 복잡도

O(v + e)

 

3) 실수

 

4) 배운점

 

5) PS

---

정답 코드

#include <bits/stdc++.h>

using namespace std;

int r, c, v, o;
const int MAX = 255;
string board[MAX];
bool visited[MAX][MAX];

int moveY[] = {-1,0,1,0};
int moveX[] = {0,-1,0,1};

void BFS(int i, int j){
    queue<pair<int,int>> q;
    q.push({i, j});
    visited[i][j] = true;
    int curV = 0, curO = 0;
    while(!q.empty()){
        auto[y, x] = q.front();
        q.pop();
        if(board[y][x] == 'v')
            curV++;
        if(board[y][x] == 'o')
            curO++;

        for(int d = 0; d < 4; d++){
            int ny = y + moveY[d];
            int nx = x + moveX[d];
            if(ny >= 0 && ny < r && nx >= 0 && nx < c){
                if(!visited[ny][nx] && board[ny][nx] != '#'){
                    visited[ny][nx] = true;
                    q.push({ny, nx});
                }
            }
        }
    }

    if(curV >= curO){
        v += curV;
    }else{
        o += curO;
    }
}

void pro(){
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++) {
            if (!visited[i][j] && board[i][j] != '#') {
                BFS(i, j);
            }
        }
    }
}

void input(){
    cin >> r >> c;
    for(int i = 0; i <r; i++){
        cin >> board[i];
    }
}

int main(){
    input();
    pro();
    cout << o <<" " << v <<"\n";
}