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

www.acmicpc.net/problem/1926

1926번: 그림

 

기초적인 BFS문제입니다. 

제가 전부 생각해 낸게 아니라 기초 알고리즘을 비롯해 문제에 대한 도움을 받고 이 문제를 풀었습니다.

아래에 출처를 표시했습니다.

 

우선 board와 방문 표시를 위한 visit 배열을 선언하고,

각 칸의 상하 좌우를 살피기 위해 dx, dy를 선언했습니다.

우선 가장 먼저 방문하는 곳을 (x,y)라고 정했습니다.

이후 아래(x+1,y), 오른쪽(x,y+1), 위(x-1,y), 왼쪽(x,y-1) 순서로 배열에 인덱스를 저장했습니다.

 

max_area: 가장 넓이가 큰 그림을 카운팅 하기 위한 변수

num: 그림의 갯수를 카운팅 하기 위한 변수

 

이중 for문으로 각 칸을 모두 돌면서 그림의 시작을 찾습니다. 

만약 첫 시작을 찾았다면, 그 칸의 인접요소들을 모두 확인합니다.

queue에서 pop되는 만큼이 한 그림의 넓이임을 알 수 있습니다.

만약 이전에 구한 max_area보다 큰 넓이 값이 나오면 값을 업데이트 해줍니다.

 

코드는 아래와 같습니다. 

#include <iostream>
#include <queue>
using namespace std;

int board[502][502];
bool visit[502][502];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(void){
    int n,m;
    cin>>n>>m;
    int max_area=0;
    int num=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>board[i][j];//board채움
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(board[i][j]!=1||visit[i][j]) continue;
            queue<pair<int,int>> q;
            num++;//그림 개수++
            visit[i][j]=1;//방문 표시
            q.push({i,j});//큐에 삽입
            int temp=0;//각 그림의 넓이 계산
            while(!q.empty()){
                pair<int,int> cur=q.front();
                q.pop();
                temp++;
                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]!=1||visit[nx][ny]) continue;
                    visit[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
            if(max_area<temp) max_area=temp;  
        }
    }
    cout<<num<<"\n"<<max_area;
}

바킹독님의 알고리즘 강좌를 보면서 공부하고 혼자 풀어봤는데.. 거의 외우다시피 됐습니다.

아래의 강좌를 참고했습니다!

blog.encrypted.gg/941?category=773649

[실전 알고리즘] 0x09강 - BFS