[BOJ 1303] 전쟁 - 전투 C++

난이도: Silver 1
번호: 1303
생성일: March 19, 2023 12:31 AM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

1303번: 전쟁 - 전투

C++

#include <iostream>
#include <queue>
using namespace std;

int N, M;
char map[102][102];
bool visit[102][102];

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int BFS(int i, int j, char c)
{
    queue<pair<int, int>> Q;
    int cnt = 1;
    Q.push({i, j});
    visit[i][j] = true;

    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + cur.first;
            int y = dy[k] + cur.second;

            if (visit[x][y] || map[x][y] != c)
                continue;

            Q.push({x, y});
            visit[x][y] = true;
            cnt++;
        }
    }
    return cnt;
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    int B = 0, W = 0;
    // 세로 크기 M
    // 가로 크기 N
    cin >> M >> N;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> map[i][j];

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            int tmp;
            if (visit[i][j])
                continue;
            if (map[i][j] == 'W')
            {
                tmp = BFS(i, j, 'W');
                W += tmp * tmp;
            }
            else if (map[i][j] == 'B')
            {
                tmp = BFS(i, j, 'B');
                B += tmp * tmp;
            }
        }
    cout << W << " " << B;
}