[백준]Q1926

2021-01-05

Baekjoon
Algorithms

문제
입력
- 출력
- 코드

문제

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

입력

출력

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

코드

n,m과 board배열 입력
그림이 아니거나(board[i][j] == 0) 방문한 적 있을 때(isVisit[i][j] == 1) → continue
방문하지 않은 그림일 때
1. picNum++; → 상하좌우 더이상 연결된 것이 없는 범위까지가 그림임
2. queue 를 만들어서 방문하지 않은 좌표들을 담는다.
3. queue에 삽입했다면 isVisit에 해당 좌표 방문처리를 한다.
4. 최신 좌표를 꺼낸 후, 큐에서 삭제한다.
5. 최신 좌표의 상하좌우를 돌며, 방문하지 않은 그림의 좌표를 큐에 삽입한다.
6. 큐가 전부 빌 때 까지 반복

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

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int board[502][502];
bool isVisit[502][502];
int n, m;
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> board[i][j];
        }
    }
    int picNum = 0; // 그림의 수
    int maxPic = 0; // 그림 최댓값
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            // 그림이 아니거나 방문한 적 있는 경우
            if(board[i][j] == 0 || isVisit[i][j]) continue;
            picNum++;
            queue<pair<int, int>> q;
            isVisit[i][j] = 1;
            q.push({i, j});
            int area = 0; // 그림의 넓이
            // 인접 칸을 다 돌 때 까지
            while(!q.empty()) {
                area++;
                pair<int, int> current = q.front();
                q.pop();
                for(int dir=0;dir<4;dir++) {
                    int nearX = current.first + dx[dir];
                    int nearY = current.second + dy[dir];
                    if(nearX < 0 || nearX >=n || nearY <0 || nearY >=m) continue;
                    if(isVisit[nearX][nearY] || board[nearX][nearY]!=1) continue;
                    isVisit[nearX][nearY] = 1;
                    q.push({nearX, nearY});
                }
            }
            // (i, j) 를 시작점으로 하는 BFS 종료
            maxPic = max(maxPic, area);
        }
    }
    cout << picNum << "\\n" << maxPic;
    return 0;
}