백준_3184(bfs).md

백준_3184(bfs)

---

#include <iostream>
#include <queue>

using namespace std;
const int MAX = 250;
typedef struct
{
    int x, y;
} Dir;
typedef struct
{
    int x, y;
} Point;

Dir dirMove[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
string graph[MAX];
bool visited[MAX][MAX];
int R, C;
int sheepNum;
int wolfNum;
int final_sheepNum;
int final_wolfNum;

void bfs(int x, int y)
{
    queue<Point> q;
    visited[x][y] = true;
    q.push({x, y});
    if (graph[x][y] == 'o')
        sheepNum++;
    if (graph[x][y] == 'v')
        wolfNum++;
    while (!q.empty())
    {
        Point nextPoint = q.front();
        q.pop();
        int currX = nextPoint.x;
        int currY = nextPoint.y;

        for (int i = 0; i < 4; i++)
        {
            int nextX = currX + dirMove[i].x;
            int nextY = currY + dirMove[i].y;
            if (0 <= nextX && nextX < R && 0 <= nextY && nextY < C)
            {
                if (!visited[nextX][nextY] && graph[nextX][nextY] != '#')
                {
                    if (graph[nextX][nextY] == 'o')
                    {
                        q.push({nextX, nextY});
                        visited[nextX][nextY] = true;
                        sheepNum++;
                    }
                    else if (graph[nextX][nextY] == 'v')
                    {
                        q.push({nextX, nextY});
                        visited[nextX][nextY] = true;
                        wolfNum++;
                    }
                    else if (graph[nextX][nextY] == '.')
                    {
                        q.push({nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        cin >> graph[i];
    }
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (graph[i][j] == 'o' || graph[i][j] == 'v')
            {
                if (!visited[i][j])
                {
                    bfs(i, j);
                    // cout << sheepNum << " " << wolfNum << "\n";
                    if (sheepNum > wolfNum)
                        final_sheepNum += sheepNum;
                    else
                        final_wolfNum += wolfNum;
                    sheepNum = 0;
                    wolfNum = 0;
                }
            }
        }
    }
    cout << final_sheepNum << " " << final_wolfNum;
}

전형적인 bfs 문제.

 else if (graph[nextX][nextY] == '.')
 {
     q.push({nextX, nextY});
     visited[nextX][nextY] = true;
 }

이 부분을 넣지 않아서 계속 오류가 났었다....