(매일 BOJ) C++ 1926번 그림

이번 문제는 1926번 그림이

문제 요약

세로 x, 가로 y 크기의 2차원 격자에서 값이 1인 칸들을 상하좌우로 연결된 묶음(연결요소)으로 정의한다. 

1. 그림(연결요소)의 총 개수와
2. 가장 큰 그림의 넓이(포함 칸 수)
   를 계산하여 출력해야 함

접근법

모든 칸을 순회하면서 값이 1이고 아직 방문하지 않은 시작점을 발견할 때마다 BFS를 수행하여 해당 연결요소 전체를 탐색한다 BFS 과정에서 방문할 때마다 면적 변수를 1씩 증가시키고, 탐색 종료 시 최대 넓이를 갱신한다. 각 칸은 최대 한 번만 방문하므로 전체 시간 복잡도는 O(x⋅y)가 된다

 

알고리즘 설계

1. 입력으로 x,y 및 x×y 격자를 수신
2. 방문 배열을 초기화
3. 이중 반복으로 모든 좌표 (i,j)(i, j)(i,j)를 순회
   • graph[i][j]==1 이고 미방문이면, 해당 좌표를 시작점으로 BFS를 수행
   • BFS 중 큐에서 좌표를 꺼내 4방향(상하좌우)으로 인접한 유효 좌표를 검사하고, 값이 1이면서 미방문이면 방문 처리 후 큐에 삽입하고 면적 증가
4. 각 BFS 종료 시 그림 개수를 1 증가시키고, 최대 넓이를 갱신
5. 모든 탐색이 종료되면 그림 개수와 최대 넓이를 출력

작성코드

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

pair<int, int> BFS (vector<vector<int>> & graph);
int x,y;
int fourway_x[4] = {0,0,1,-1};
int fourway_y[4] = {1,-1,0,0};

int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> x >> y;
    vector<vector<int>> graph(x,vector<int>(y));  
    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            int a;
            cin >> a; 
            graph[i][j] = a;
        }
    }

    pair<int, int> p = BFS(graph);
    cout << p.first << '\n' << p.second;

    return 0;
}

pair<int, int> BFS (vector<vector<int>> & graph){
    vector<vector<bool>> visited(x,vector<bool>(y,false));
    queue<pair<int,int>> q;
    int count_group = 0, max_group = 0;

    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){ 
            if(graph[i][j] == 1 && !visited[i][j]){

                visited[i][j] = true;
                count_group += 1;
                q.push({i,j});
                int area = 1;

                while(!q.empty()){
                    int current_x = q.front().first;
                    int current_y = q.front().second;
                    q.pop();

                    for(int o = 0; o < 4; o++){
                        int next_x = fourway_x[o] + current_x;
                        int next_y = fourway_y[o] + current_y;

                     if(next_x >= 0 && next_y >= 0 && next_x < x && next_y < y && !visited[next_x][next_y] && graph[next_x][next_y] == 1){
                            area += 1;
                            visited[next_x][next_y] = true;
                            q.push({next_x,next_y});
                        }
                    } 
                }
                max_group = max(max_group,area);
            }
        }
    }
    return {count_group,max_group};
}