[백준/C++] 1926번 그림

문제: www.acmicpc.net/problem/1926

1926번: 그림

 

 

문제풀이

 

BFS 알고리즘으로 문제를 풀었다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m;
    cin>>n>>m;

    int visited[500][500] = {0,};
    int board[500][500];
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    int area, cnt = 0, maxArea = 0;

    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(visited[i][j] || board[i][j] == 0) continue;

            cnt++; //새로운 그림을 만났으므로 cnt++
            area = 0; //그림 크기 초기화

            queue<pair<int, int>> q;
            visited[i][j] = 1;
            q.push({i,j});

            while(!q.empty()){
                area++; //큐가 지속된다면 그림이 연결되어있다는 뜻으로 그림 크기 증가

                pair<int, int> cur = q.front();
                q.pop();

                for(int dir=0; dir<4; dir++){
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];

                    if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if(board[nx][ny] == 0 || visited[nx][ny]) continue;

                    visited[nx][ny] = 1;
                    q.push({nx,ny});
                }
            }

            if(maxArea < area) //최대 그림 크기 저장
                maxArea = area;
        }
    }

    cout<<cnt<<"\n"<<maxArea;
    

    return 0;
}

 

 

결과