2022-07-21-paint-1926

• toc {:toc}

문제

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

입력

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

출력

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

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

풀이

BFS (Breadth First Search)

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

빠짐없이 방문할 때 너비를 우선으로 방문한다.

구현 과정

1. 시작하는 칸을 큐에 넣고 방문표시를 한다.
2. 큐에서 원소를 꺼내 해당 원소의 칸의 상하좌우 칸에 대해 3번을 진행한다.
3. 해당 칸을 이전에 방문했다면 pass하고 처음 방문하면 방문했다는 표시를 남기고 큐에 삽입한다.
4. 큐가 빌 때까지 2번을 반복한다.

모든 칸이 큐에 1번씩 들어가기 때문에 BFS에 대한 시간복잡도는 칸이 N개 일 때 O(N)

#include <bits/stdc++.h>
using namespace std;
 
#define X first
#define Y second
 
int vis[502][502];              // 방문 확인 배열
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
queue<pair<int, int> > q;       // 2차원 배열이므로 pair 사용
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie();
    int n, m, val;
    int board[502][502];
    cin >> n >> m;
    for(int i = 0; i < n; i++){         // 보드판에 값 입력
        for(int j = 0; j < m; j++){
            cin >> val;
            board[i][j] = val;
        }
    }
    int cnt = 0, area = 0;
    for(int row = 0; row < n; row++){   
        for(int col = 0; col < m; col++){
            int temp = 0;
            if(vis[row][col] != 0 || board[row][col] != 1) continue;    // 초기값 설정
            vis[row][col] = 1;
            q.push({row, col});
            cnt++;
            while(!q.empty()){                  // 2~4번 과정
                pair<int, int> cur = q.front();
                q.pop();
                temp++;
                for(int dir = 0; dir < 4; dir++){
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
            if(area < temp) area = temp;
        }
    }
    cout << cnt << endl;
    cout << area << endl;
}