[백준 3184] 양

[백준 3184] 양

문제 링크

#include "header.h"
using namespace std;
int R, C;
//'.' 빈 필드
//'#' 울타리
//'o' 양
//'v' 늑대
int ans_wolf, ans_sheep;
char fence[251][251];
int visit[251][251];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void input(){
    cin >> R >> C;

    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> fence[i][j];
        }
    }
}
void bfs(int x, int y){
    queue <pair<int, int>> q;
    visit[x][y] = 1;
    q.push({x, y});

    int sheep = 0;
    int wolf = 0;

    if(fence[x][y] == 'o') sheep++;
    if(fence[x][y] == 'v') wolf++;

    while(!q.empty()){
        int top_x = q.front().first;
        int top_y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];

            if(visit[nx][ny] || fence[nx][ny] == '#' || nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

            if(fence[nx][ny] == 'o') sheep++;
            if(fence[nx][ny] == 'v') wolf++;

            q.push({nx, ny});
            visit[nx][ny] = 1;
        }
    }

    // 영역 안의 양의 수가 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.
    // 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

    if(wolf >= sheep){
        ans_wolf += wolf;
    }else ans_sheep += sheep;

}
void solve(){

    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(fence[i][j] != '#' && !visit[i][j]){
                bfs(i, j);
            }
        }
    }
}

int main()
{
    input();
    solve();

    cout << ans_sheep << ' ' << ans_wolf << endl;
    return 0;
}

• 1년 전에 못 풀었는데 이젠 풀 수 있다!! :D
• 전체를 돌면서 방문하지 않았고, 울타리가 아닌 경우에 bfs를 돌아 준다.
• bfs 내부에서 양과 늑대의 수를 세고,
• 큐가 비었을 때 (범위 탐색이 끝났을 때) 비교 해주어 답을 갱신한다.