백준 1303 전쟁 - 전투 (C++)

안유태·2023년 10월 23일
0

알고리즘

목록 보기
162/239

1303번: 전쟁 - 전투

bfs를 이용한 문제이다. 기존 bfs 흐름과 같다. 반복문을 돌면서 BW 그륩들을 각각 카운트하여 제곱을 한 후 더해주고 출력을 해주면 된다. 간단하게 풀 수 있었던 문제였다.



#include <iostream>
#include <queue>

using namespace std;

int N, M;
string A[100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool check[100][100];
int sumw = 0, sumb = 0;

void bfs(int a, int b) {
    queue<pair<int, int>> q;
    char bw = A[a][b];
    int count = 1;

    q.push({ a,b });
    check[a][b] = true;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
            if (check[ny][nx]) continue;
            if (bw != A[ny][nx]) continue;

            q.push({ ny,nx });
            check[ny][nx] = true;
            count++;
        }
    }

    if (bw == 'W') sumw += (count * count);
    if (bw == 'B') sumb += (count * count);
}

void solution() {
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (check[i][j]) continue;

            bfs(i, j);
        }
    }

    cout << sumw << " " << sumb;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글