[백준] 양 3184번 (c++)

출처 : 3184번: 양 (acmicpc.net)

3184번: 양

풀이 방법

조건 몇 가지만 추가해서 bfs로 풀이할 수 있다.

board전체를 for 문을 통해 돌며 #이 아니며 방문한 적이 없다면 bfs를 호출 한다.

board[y][x]가 양이면 sheep변수에 +1 board[y][x]가 늑대이면 wolf변수에 +1을 해주고

bfs가 종료되기 전에 sheep의 변수 값이 큰지 wolf의 변수 값이 큰지 비교해서 

sheep이 크면 n_sheep(전체 양이 몇 마리인지 저장하는 글로벌 변수)에 + sheep을 해주고

wolf가 크면 n_wolf(전체 늑대가 몇 마리인지 저장하는 글로벌 변수)에 +wolf를 해준다.

이 과정을 마무리하면 n_sheep과 n_wolf를 출력해 준다.

#include <bits/stdc++.h>
using namespace std;

int R, C;
char board[251][251];
int visited[251][251];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n_wolf, n_sheep;

void bfs(int y, int x) {
    int sheep = 0, wolf = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    visited[y][x] = 1;
    if (board[y][x] == 'v') wolf++;
    if (board[y][x] == 'o') sheep++;
    while(!q.empty()) {
        int nowy = q.front().first;
        int nowx = q.front().second;
        q.pop();
        for(int i = 0;i < 4;i++) {
            int yy = nowy + dy[i];
            int xx = nowx + dx[i];
            if (yy >= 0 && yy < R && xx >= 0 && xx < C && visited[yy][xx] == -1 && board[yy][xx] != '#') {
                if (board[yy][xx] == 'o') {
                    sheep++;
                }
                if (board[yy][xx] == 'v') {
                    wolf++;
                }
                visited[yy][xx] = 1;
                q.push(make_pair(yy, xx));
            }
        }
    }
    if (sheep > wolf) {
        n_sheep = n_sheep + sheep;
    }
    else {
        n_wolf = n_wolf + wolf;
    }
}

int main() {
    cin >> R >> C;
    memset(visited, -1, sizeof(visited));
    for (int i = 0;i < R;i++) {
        for (int k = 0;k < C;k++) {
            cin >> board[i][k];
        }
    }
    for (int i = 0;i < R;i++) {
        for (int k = 0;k < C;k++) {
            if(board[i][k] != '#' && visited[i][k] == -1) {
                    bfs(i, k);
            }
        }
    }
    cout << n_sheep << " " << n_wolf;
    return 0;

}