문제

• 도화지에 그려진 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이 출력
• 1로 연결된 것을 한 그림으로 정의
• 가로나 세로로 연결된 것은 연결이 된 것
• 대각선으로 연결이 된 것은 떨어진 그림

입력

• 첫째 줄 : 도화지의 세로크기 X 도화지 가로크기가 주어짐
• 둘째 줄: n+1줄까지 그림의 정보 주어짐
  0과 1이 공백을 두고 주어지며 0은 색칠이 안된 부분, 1은 색칠이 된 부분
  

출력

• 첫째줄: 그림의 개수
• 둘째줄: 가장 넓은 그림의 넓이 출력
  그림이 하나도 없는 경우 가장 넓은 그림의 넓이 ==0

예제 입력

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

풀이

풀이 1

1. 그림을 입력받을 수 있는 배열 n*m을 만들어 그림상태를 입력받는다.

2. 그림의 각 격자에 방문여부를 저장하기 위해 n*m 크기의 2차원 벡터를 만들어 모두 0으로 초기화한다.

3. for(int i=0; i<n;)
   for(int j=0; j<m;)
   if(그림이 1 && 방문한 적이 없으면){
   scale++;
   isVisit[i][j]=1; //해당 인덱스를 방문함으로 바꿈
   if(L ==1 && 방문한적이 없으면) j--; continue;
   else if(R ==1 && 방문한적이 없으면) j++; continue;
   else if(U ==1 && 방문한적이 없으면) i--; continue;
   else if(D ==1 && 방문한적이 없으면) i++; continue;
   else (이동할 수 있는 곳이 없을 때)
   그림개수 painting++;
   if(maxScale < scale) maxScale = scale;
   j++;

   i++;

#include <bits/stdc++.h>
using namespace std;
int arr[502][502]; //그림
int isVisit[502][502]; //방문여부 저장

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    //그림 입력받기
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> arr[i][j]; //1또는 0
        }
    }
    
    int scale;
    int maxScale =0;
    int painting=0; //그림 개수
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(arr[i][j]==1 && isVisit[i][j]==0){
                scale++;
                isVisit[i][j]=1;
                
                if(arr[i][j-1]==1 && isVisit[i][j-1]==1) { //L
                    j-=2; continue;
                }
                else if(arr[i][j+1]==1 && isVisit[i][j+1]==1) { //R
                    continue;
                }
                else if(arr[i-1][j]==1 && isVisit[i-1][j]==1) { //U
                    i-=2; continue;
                }
                else if(arr[i+1][j]==1 && isVisit[i+1][j]==1) { //D
                    i++; continue;
                }
                
                else {//이동할 수 있는 곳이 없을 때
                    painting++;
                    if(maxScale<scale){
                        maxScale=scale; 
                        scale=0; //크기 초기화
                    }
                }
            
            }
            
        }
    }
    

    cout << painting<<'\n';
    cout << maxScale;
    
    
    
    
    return 0;
}

풀이 2

정석적 bfs 틀을 사용하여 작성

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[502][502]; //그림
int isVisit[502][502]; //방문여부 저장

//아래 오른쪽 위 왼쪽
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n>>m;
    
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> board[i][j];
    
    int maxScale=0; //그림의 최대크기 
    int paintings=0; //그림 갯수
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            //0이거나 방문한 경우
            if(board[i][j]==0 || isVisit[i][j]) continue;
            
            paintings++;
            
            queue<pair<int, int>> Q;
            //1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
            isVisit[i][j]=1;
            Q.push({i,j});
            
            int scale =0; 
            while(!Q.empty()){
                scale++;
                // 큐에 들어있는 원소를 하나 뺄 때 마다 넓이를 1 증가시킴
                pair<int, int> current = Q.front(); 
                Q.pop();
                
                
                //2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
                for(int dir =0; dir<4; dir++){
                    //nx: 다음 x, ny: 다음 y
                    int nx = current.X + dx[dir];
                    int ny = current.Y + dy[dir];
                    
                    //범위 밖으로 벗어나지 않게 if문 걸어주기
                    if(nx <0 ||nx>=n || ny<0|| ny>=m) continue;
                    //방문했거나 색칠된 칸이 아닌경우
                    if(isVisit[nx][ny] || board[nx][ny]!=1)continue;
                    
                    isVisit[nx][ny] = 1; //다음칸 방문 명시
                    Q.push({nx, ny}); //큐에 push
                }
            }
            
            //(i,j)를 시작점으로 하는 bfs 종료
            maxScale = max(maxScale, scale);
        }
    }
    
    cout << paintings << '\n'<<maxScale;
    
    
}