[백준] 16932 모양 만들기

 

시간이 충분한 문제다

 

내가 0일 때 그리고 1일 때 경우를 나눠서 생각하면 된다

 

먼저 모양의 수는 어떻게 정할까?

 

유니온 파인드를 이용하면 쉽게 찾을 수 있다

 

merge할 때마다 해당 부모의 수도 합치면 된다

 

그렇게 미리 크기를 구해두고

 

모든 정점에서 만약 해당 정점이 1이면 해당 부모의 크기

0이면 4방향 부모의 합+ 1=>(나를 1로바꿨을때) 을 하면서 최댓값을 찾아보자!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int arr[1010][1010];
int p[1010*1010];
int cnt[1010*1010];
bool check[1010][1010];
bool pick[1010*1010];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 
bool inner(int x,int y){
    return (0<= x && x<n && 0<=y && y<m);
}
 
int find(int x){
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
}
 
void merge(int x,int y){
    x=find(x); y=find(y);
    if(x==y) return; 
    p[x]=y;
    cnt[y]+=cnt[x];
}
 
void dfs(int x,int y){
    check[x][y]=true;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(inner(nx,ny) && !check[nx][ny] && arr[nx][ny]){
            merge(find(x*m+y),find(nx*m+ny)); dfs(nx,ny);
        }
    }
}
 
int main(){
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %d",&arr[i][j]);
            p[i*m+j]=i*m+j;
            cnt[i*m+j]=arr[i][j];
        }
    }
 
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j] && !check[i][j]) dfs(i,j);
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]) ans =max(ans,cnt[find(i*m+j)]);
            else{
                int temp=1;
                for(int k=0;k<4;k++){
                    int nx = i+dx[k];
                    int ny = j+dy[k];
                    if(inner(nx,ny)) pick[find(nx*m+ny)]=true; 
                }
                for(int k=0;k<4;k++){
                    int nx = i+dx[k];
                    int ny = j+dy[k];
                    if(inner(nx,ny) && pick[find(nx*m+ny)]){
                        temp+=cnt[find(nx*m+ny)]; pick[find(nx*m+ny)]=false;
                    } 
                }
                ans = max(ans,temp);
            }
        }
    }
    printf("%d\n",ans);
}