백준 1926 그림 (C++)

안유태·2023년 7월 28일
0

알고리즘

목록 보기
122/239

1926번: 그림

bfs를 이용한 문제이다. 반복문을 돌면서 A 배열이 true일 경우 bfs를 돌려주며 넓이를 계산해주고 큰 값을 저장해주었다. 동시에 그림의 개수도 카운트 해주었고 넓이와 갯수를 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.



#include <iostream>
#include <queue>

using namespace std;

int n, m, ms = 0;
bool A[500][500];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

void bfs(int a, int b) {
    queue<pair<int, int>> q;
    int ss = 1;

    q.push({ a,b });
    A[a][b] = false;

    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 >= n || nx >= m) continue;
            if (!A[ny][nx]) continue;

            q.push({ ny,nx });
            A[ny][nx] = false;
            ss++;
        }
    }

    ms = ss > ms ? ss : ms;
}

void solution() {
    int count = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!A[i][j]) continue;

            bfs(i, j);
            count++;
        }
    }

    cout << count << endl;
    cout << ms << endl;
}

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

    cin >> n >> m;

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

    solution();

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

0개의 댓글