[백준] 1926번 그림

문제 링크: https://www.acmicpc.net/problem/1926

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

문제 이해

map이 주어지고, 그 map에 그림의 조각이 있는 구간들은 1로 표시가 된다. 그리고 상하로 연결되어 있는 1은 하나의 그림이 된다. map에 그림의 개수와 가장 큰 그림의 크기를 구하는 문제이다.

문제 접근

1. 입력 받기. N X M 짜리 맵이 존재하고 그림 조각이 있는 곳은 1로 표시한다.
2. for문으로 N X M 맵 검사하기. 검사 중 map에 1로 표시되어 있고, 전에 check한 곳이 아니라면, queue에 넣고 bfs. 그림 개수++
3. bfs 시작. 그림 조각이 나올 때마다 size++
4. size 비교하여 maxSize 찾기.

코드 구현(c++)

#include <iostream>
#include <queue>

using namespace std;
int map[501][501];
int check[501][501] = {0,};
typedef struct Coordinate{
    int x;
    int y;
}coordinate;

queue<coordinate> q;
int xCheck[4] = {-1,0,0,1};
int yCheck[4] = {0,-1,1,0};
int maxSize = 0;
int cnt = 0;
int N,M;

void bfs(){
    coordinate temp;
    coordinate pushCoordinate;
    int x,y;
    int size = 1;
    while(!q.empty()){
        temp = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ; i++){
            x = temp.x + xCheck[i];
            y = temp.y + yCheck[i];
            if(x >= 0 && y  >= 0 && x < N && y < M){
                if(check[x][y] == 0 && map[x][y]){
                    check[x][y] = 1;
                    pushCoordinate.x = x;
                    pushCoordinate.y = y;
                    q.push(pushCoordinate);
                    size++;
                }
            }
        }
    }
    if(maxSize < size) maxSize = size;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    
    cin >> N >> M;
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            cin >> map[i][j];
        }
    }
    coordinate temp;
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            if(map[i][j] == 1 && check[i][j] == 0){
                temp.x = i;
                temp.y = j;
                q.push(temp);
                check[i][j] = 1;
                bfs();
                cnt++;
            }
        }
    }
    cout << cnt << "\n" << maxSize << "\n";
}

평가

첫 bfs문제를 풀었다. 어떻게 구현할 지 감이 안잡혀, 작년 알고리즘 시간에 배웠던 ppt를 보면서, 구현을 하였다. 그래서인지 코드를 깔끔하게 구현한 거 같아 기분이 좋았다. 이번주는 BFS와 DFS위주의 알고리즘 문제를 풀 예정이다.
Graph에 대한 내용 정리도 한번 할 예정이다.