[boj : 16932]모양 만들기

[문제]:https://www.acmicpc.net/problem/16932

16932번: 모양 만들기

#2021/02/05 코드와 로직 수정

 

[분류] : 탐색(DFS)

 

[조건]:

0으로 채워진 칸을 1로 바꾸었을때 연속적으로 존재하는 1의 개수가 가장 최대임을 찾으면 됩니다.

 

[과정] :

1)먼저 연속적으로 붙어있는 1로 채워진 칸들이 존재한다면 이들을 구분해 주기 위해 그룹화를 진행해야 된다.(그룹화를 진행 해야되는 이유는 '구현방법'에서 설명하겠습니다.)

2)그룹화가 된 요소들의 수를 map에다가 저장해 줍니다 (1번 그룹 : x개) / (2번 그룹 :  y개) .........

===> 이때 주의할점은 탐색 시작 시점도 포함해서 세어주어야 합니다.

3)격자가 0 인 지점부터 다시 탐색을 시작하여 4방향(상하좌우)를 확인합니다. 그리고 set을 이용하여 중복된 그룹을 걸러내는 것이죠.

4)그렇게 합을 구해준 후 최대값을 매번 갱신해주어 답을 도출하면 됩니다.

 

이 문제 전 개인적으로 너무 힘들었습니다....아직 멀었다는 걸 느낀 문제입니다 ㅠㅠ

일단 처음에 만만히 보고 DFS로 풀면 되겠지 하고 풀었습니다.하지만 바로 '시간초과'가 발생 하더라구요.

1의 개수를 M이라고 했을때 시간 초과가 발생하는 이유는 바로 시간 복잡도가 약 O((NM)^2)이 될 수도 있기 때문입니다.

 

예를 들어 보겠습니다.

 

0 1 0 1 0 1 ............. 0 1 0 1 0 1

1 1 1 1 1 1 ............. 1 1 1 1 1 1

0 1 0 1 0 1 ............. 0 1 0 1 0 1

1 1 1 1 1 1 ............. 1 1 1 1 1 1

 .

 .

 .

1 1 1 1 1 1 ............. 1 1 1 1 1 1

0 1 0 1 0 1 ............. 0 1 0 1 0 1

 

이런식으로 입력이 들어오게 된다면 매번 방문체크를 해주어야 되는 visit 함수를 초기화 하면서 진행하기에는 무리가 있습니다.따라서 이를 해결하기 위한 방법이 수들의 '그룹화'입니다.

방법은 이렇습니다.

 

연속적인 1들을 구분해 주기 위해 수들로 구분합니다.예제로 설명하면

1 1 0 0

1 0 1 0

1 0 1 0

0 1 1 0

       1 0 0 1       

이런식으로 입력이 들어오게 되면 

1 1 0 0

1 0 2 0

1 0 2 0

0 2 2 0

3 0 0 4

이렇게 그룹화를 완성시켜 주면 됩니다.이 그룹화를 완성시켜 주는 과정은 평범하게 DFS를 이용해서 만들어 주면 되겠죠. 그러면서 동시에 그룹의 원소의 수를 배열에 미리 저장해 둡니다.

그 후는 소스에서 참고하시길 바라겠습니다.

 

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

int n,m;
int board[1000][1000],visit[1000][1000];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
map<int,int> mp;

int go();
void bfs(int x,int y,int k);
void input();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	input();
	cout<<go();
	return 0;
}
int go()
{
	int cnt=0,ans=0,sum=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(!visit[i][j]&&board[i][j]==1)
				bfs(i,j,++cnt);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			if(board[i][j]==0){
				set<int> s;
				for(int k=0;k<4;k++){
					int tx = i+dx[k];
					int ty = j+dy[k];
					
					if(tx<0 || tx>=n || ty<0 || ty>=m)continue;
					
					if(board[tx][ty]!=0 && s.find(board[tx][ty])==s.end()){
						s.insert(board[tx][ty]);
						sum+=mp[board[tx][ty]];
					}
				}
			}
			ans=max(ans,sum);
			sum=0;
		}
	return ans+1;	
}
void bfs(int x,int y,int k)
{
	int cnt=0;
	queue<pair<int,int>> q;
	q.push({x,y});
	visit[x][y]=1;
	board[x][y]=k;
	
	while(!q.empty())
	{
		pair<int,int> cur = q.front();
		q.pop();
		
		for(int i=0;i<4;i++){
			int tx = cur.first+dx[i];
			int ty = cur.second+dy[i];
			
			if(tx<0 || tx>=n || ty<0 || ty>=m)continue;
			
			if(!visit[tx][ty] && board[tx][ty]!=0){
				visit[tx][ty]=1;
				board[tx][ty]=k;
				q.push({tx,ty});
				cnt++;
			}
		}
	}
	mp[k]=cnt+1;
}
void input()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)cin>>board[i][j];
}

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다