[백준 1926] 그림 (C++)

예제 입력

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

이 문제는 Flood Fill 문제인 것이 쉽게 드러난다. 따라서, BFS나 DFS로 접근하면 문제를 해결할 수 있을 것이다. 필자는 편의상 BFS 풀이만 다룰 것이다.

먼저, 모든 그림들에 대하여, Flood Fill로 넓이를 구하고, 최대 넓이를 갱신하는 방식으로 접근하면 된다.

하지만, 이는 시작점이 여러 개인 BFS이므로 이에 대한 처리로 1이면서 방문한 적이 없는 지점을 시작점으로 잡아야 한다. 이를 위해, vis[501][501]을 방문 여부를 저장하는 배열로 선언하고 사용하자.

그리고, BFS의 시작점을 파악했다면, 이를 점인 x0, y0부터 BFS를 시작하자.
참고로, 인접한 위치를 손쉽게 계산하기 위해 dx, dy 테크닉을 사용하도록 한다.

다음 위치인 nx, ny가 도화지를 벗어난다면 다음으로 넘어가고,
그렇지 않다면, 방문하지 않은 1인 경우에만 큐에 저장하고, 방문했다 기록한 뒤, 넓이를 1 증가시키자.

이후, 넓이를 리턴하는 것으로 BFS는 끝이 난다.

#include <bits/stdc++.h>
using namespace std;

int mx_area, n, m, tot;
bool board[501][501], vis[501][501];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int bfs(int x0, int y0) {
    queue<pair<int, int>> q;
    q.push({x0, y0});
    vis[x0][y0] = true;
    int area = 1;
    
    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[nx][ny] || !board[nx][ny]) continue;
            q.push({nx, ny});
            vis[nx][ny] = true;
            area++;
        }
    }
    
    return area;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> board[i][j];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j] || !board[i][j]) continue;
            mx_area = max(mx_area, bfs(i, j));
            tot++;
        }
    }
    
    cout << tot << "\n" << mx_area;
}

그림의 갯수를 세기 위해, tot라는 변수를 사용했으며, 이는 BFS 시작점의 위치 갯수와 동일하므로 이를 세는 것으로 그림의 총 갯수를 파악하자.