[백준 1926] 그림

1926번: 그림 (acmicpc.net)

1926번: 그림

 

내 풀이

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

int n, m;
int a[502][502];
bool check[502][502];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
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 >> a[i][j]; //입력 어떻게 받는지 유심히 봐
        }
    }

    int cnt=0;
    int marea=0;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]==1&&check[i][j]==false)// false 주의. 0이나 -1 이런거 ㄴㄴ bool type
            {
                cnt++;
                queue<pair<int,int>> q;
                q.push({i,j});
                check[i][j]=true;
                int area=0; // 어!?
                while(!q.empty())
                {
                    area++;
                    int x=q.front().first;
                    int y=q.front().second;
                    
                    q.pop();
                    
                    for(int i=0;i<4;i++)
                    {
                        int nx=x+dx[i];
                        int ny=y+dy[i];
                        
                        if(nx<0|| nx>=n||ny<0||ny>=m)continue;
                        if(a[nx][ny]==0||check[nx][ny]==true)continue;
                        q.push({nx,ny});
                        check[nx][ny]=true;
                    }
                }
                //섬 하나 돌았다는거야
                marea=max(marea,area); // max, min 함수 못쓰네
            }
            //얘 나오면 뭐야?
        }
    }

    cout<<cnt<<'\n'<<marea;
    
}

 

 

정답 풀이

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

int n, m;
int a[502][502];
bool check[502][502];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
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 >> a[i][j];
        }
    }

    int cnt = 0; //그림갯수
    int marea = 0; //가장넓은그림넓이

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            if (a[i][j] == 1 && check[i][j] == false)
            {
                cnt++;
                queue<pair<int, int>> q;
                check[i][j] = true;
                q.push(make_pair(i, j));
                int area = 0;
                while (!q.empty())
                {
                    area++;
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for (int i = 0; i < 4; i++)
                    {
                        int nx = x + dx[i];
                        int ny = y + dy[i];

                        if (0 <= nx && nx < n && 0 <= ny && ny < m)
                        {
                            if (a[nx][ny] == 1 && check[nx][ny] == false)
                            {
                                q.push(make_pair(nx, ny));
                                check[nx][ny] = true;
                            }
                        }
                    }
                }
                marea = max(marea, area);
            }
        }
    }
    cout << cnt << '\n' << marea;

}