[BOJ/3184번양] c++ / BFS

문제

울타리 안의 양과 늑대의 수를 비교하여 싸움을 붙인 후, 살아있는 양과 늑대의 수를 구하는 문제

 

생각

울타리 안 영역을 그룹핑해서 양 수와 늑대수 구한 뒤, 수를 비교해봐야겠다 생각함

처음 코드가 예시 답은 다 나오는데  틀렸습니다만 나옴 ..

진짜 왜 틀렸는지 모르겠음.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first 
#define Y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int R, C, cnt=0, scnt=0, wcnt=0;
string board[251];
int vis[251][251];
int o[251], v[251];
void BFS() {
    queue<pair<int, int>> Q;

    for ( int i = 0; i < R; i++ ) {
        for ( int j = 0; j < C; j++ ) {
            if ( board[i][j] == '#' || vis[i][j] ) continue;
            cnt++;
            vis[i][j] = cnt;
            Q.push({i, j});

            while(!Q.empty()) {
                pair<int, int> cur = Q.front(); Q.pop();
                
                for ( int dir = 0; dir < 4; dir++ ) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

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

                    vis[nx][ny] = cnt;
                    Q.push({nx, ny});
                }
            }
        }
    }
}
void Ck() {
    for ( int i = 0; i < R; i++ ) {
        for ( int j = 0; j < C; j++ ) {
            if ( board[i][j] == 'o' )
                o[vis[i][j]]++;
            
            else if ( board[i][j] == 'v' )
                v[vis[i][j]]++;
        }
    }

    for ( int i = 1; i <= cnt; i++ ) {
        if ( o[i] > v[i] )
            scnt += o[i];
        else
            wcnt += v[i];
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    for (int i = 0; i < R; i++ )
        cin >> board[i];

    BFS();
    Ck();
    cout << scnt << " " << wcnt;
}

 

문제풀이

1.전체 양, 늑대 수 구하기

2.영역 BFS 탐색

2-1.방문하지 않았거나, #이 아닐 경우

2-2.늑대일 경우 v++

2-3.양일 경우 o++

2-4.방문표시 + 큐에 푸쉬

3.상하 좌우 탐색해서, 방문하지 않은 #이 아닌 칸이 나오면 큐에 푸쉬 + 방문표시

3-1.늑대일 경우 v++

3-2.양일 경우 o++

4.양 늑대 수 비교

4-1.양이 늑대보다 더 많을 경우, wcnt -= v

4-2.양이 늑대보다 적거나 같을 경우, scnt -= o

5.양 수와 늑대 수 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first 
#define Y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int R, C, scnt=0, wcnt=0, o=0, v=0;
string board[252];
int vis[252][252];
void BFS() {
    queue<pair<int, int>> Q;

    for ( int i = 0; i < R; i++ ) {
        for ( int j = 0; j < C; j++ ) {
            if ( board[i][j] == '#' || vis[i][j] ) continue;
            vis[i][j] = 1;
            Q.push({i, j});
            o = 0, v = 0;
            if ( board[i][j] == 'o' ) o++;
            else if ( board[i][j] =='v' ) v++;

            while(!Q.empty()) {
                pair<int, int> cur = Q.front(); Q.pop();
                
                for ( int dir = 0; dir < 4; dir++ ) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    if ( nx < 0 || nx >= R || ny < 0 || ny >= C ) continue;
                    if ( board[nx][ny] == '#' || vis[nx][ny] ) continue;
                    if ( board[nx][ny] == 'o' ) o++;
                    else if ( board[nx][ny] =='v' ) v++;

                    vis[nx][ny] = 1;
                    Q.push({nx, ny});
                }
            }
            if ( o > v ) wcnt -= v;
            else scnt -= o;
        }
    }
}
void Ck() {
    for ( int i = 0; i < R; i++ ) {
        for ( int j = 0; j < C ; j++ ) {
            if ( board[i][j] == 'o') scnt++;
            else if ( board[i][j] == 'v' ) wcnt++;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    for (int i = 0; i < R; i++ )
        cin >> board[i];

    Ck();
    BFS();
    cout << scnt << " " << wcnt;
}