백준 3187 - 양치기 꿍(C++)

문제 링크입니다. https://www.acmicpc.net/problem/3187

3187번: 양치기 꿍

BFS를 사용해 푸는 문제였습니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

int N, M;
char map[251][251];
int check[251][251];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int W, S;

void bfs(int X, int Y, int w, int s) {
    int wolf = w, sheep = s;
    queue<pair<int, int>> q;
    check[X][Y] = 1;
    q.push({ X,Y });
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
                if (map[xx][yy] != '#' && check[xx][yy] == 0) {
                    check[xx][yy] = 1;
                    if (map[xx][yy] == 'v') wolf++;
                    else if (map[xx][yy] == 'k') sheep++;
                    q.push({ xx,yy });
                }
            }
        }
    }
    if (wolf >= sheep) S -= sheep;
    else W -= wolf;
}

void solve() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] != '#' && check[i][j] == 0) {
                if (map[i][j] == 'v') bfs(i, j, 1, 0);
                else if (map[i][j] == 'k') bfs(i, j, 0, 1);
                else bfs(i, j, 0, 0);
            }
        }
    }
    cout << S << " " << W;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'v') W++;
            else if (map[i][j] == 'k') S++;
        }
    }
    solve();
    return 0;

}

 

 

질문 및 조언 댓글 남겨주세요