백준 1926번: 그림 (C++)

https://www.acmicpc.net/problem/1926

1926번: 그림

---

Solved By: Flood-Fill

 

벽 부수고 이동하기4(16946) 문제를 풀려다가 시간 초과가 나서 해결 방법을 찾다가 Flood-Fill Algorithm의 존재를 알게 되었습니다.

 

Flood-Fill이란 주어진 시작점으로부터 연결된 영역을 찾는 알고리즘, 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘을 의미합니다.

 

이 영역을 BFS를 통해 구할 수 있는데 '왜 16946문제에서 시간을 줄일 수 있는 방법으로 쓰였냐?'를 생각해봅시다.

 

각 영역의 크기를 이미 안다면 주어진 시작점이 여러 개일 때, 중복된 영역을 계속 BFS로 탐색하며 찾는 것보다 영역에 첫 발을 들인 순간 이 칸은 어떠한 영역에 속해있음을 아는 것이 시간을 확 줄일 수 있습니다.

 

이번 문제에서는 Flood-Fill을 통해 각 영역들을 구해보았습니다. 그 과정에서 각 영역의 크기를 알아내어서 최댓값을 도출해내는 문제였습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define MAX 501
using namespace std;

int picCnt = 0;
int graph[MAX][MAX];
set<pair<int, int>> s;
int n, m;

struct Point{
    int y, x;
};

Point dir[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

int bfs(int row, int col){
    s.insert({row, col});
    queue<Point> q;
    q.push({row, col});
    
    int picArea = 1;
    
    while(!q.empty()){
        int ny = q.front().y;
        int nx = q.front().x;
        
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int dy = ny + dir[i].y;
            int dx = nx + dir[i].x;
            
            if(dy <= n && dy >= 1 && dx <= m && dx >= 1){
                if(graph[dy][dx] == 1 && s.count({dy, dx}) == 0){
                    s.insert({dy, dx});
                    q.push({dy, dx});
                    picArea++;
                }
            }
        }
    }
    
    return picArea;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> graph[i][j];
        }
    }
    
    int result = 0;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(graph[i][j] == 1 && s.count({i, j}) == 0){
                result = max(result, bfs(i, j));
                picCnt++;
            }
        }
    }
    
    cout << picCnt << '\n' << result;
    return 0;
}