백준 1926 그림(c++)

https://www.acmicpc.net/problem/1926

1926번: 그림

<코드>

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int board[501][501];
bool visit[501][501] = {false};
vector<int>v;
int wid;
int mov[4][2] ={{-1,0},{1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
	wid++;
	visit[x][y] = true;
	for(int i=0;i<4;i++)
	{
		int a = x + mov[i][0];
		int b = y + mov[i][1];
		if(a>=0 && b>=0 && a<n && b<m && !visit[a][b] && board[a][b])
		dfs(a,b);
	}
}
void bfs()
{
	bool visited[501][501] = {false};
	queue<pair<int,int>>q;

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(board[i][j] && !visited[i][j])
			{
				q.push({i,j});
				int cnt=1;
				visited[i][j] = true;
				while(!q.empty())
				{
					pair<int,int> cur = q.front();
					q.pop();
					for(int k=0;k<4;k++)
					{
					int sr = cur.first + mov[k][0];
					int sc = cur.second + mov[k][1];
		
					if(sr>=0 && sc>=0 && sr<n && sc<m && !visited[sr][sc] && board[sr][sc])
					{
						visited[sr][sc]=true;
						q.push({sr,sc});
						cnt++;
					}
			
				}
				
				}
				v.push_back(cnt);
			}
		
	}
}
}

int main()
{
	cin>>n>>m;
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			
			cin>>board[i][j];
			
		}
	}
	int num=0;
	int result=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(!visit[i][j] && board[i][j])
			{
				num++;
				wid = 0;
				dfs(i,j);
				if(wid>result){
					result = wid;
				}	
			}
		}
	}
	cout<<num<<'\n';
	cout<<result<<'\n';
	bfs();
	cout<<v.size()<<'\n';
	int max = *max_element(v.begin(),v.end());
	cout<<max<<'\n';
	
}

<문제 풀이>

이 문제는 재귀호출을 이용한 dfs와 큐를 이용한 bfs 방식으로 모두 구현할 수 있다.

dfs를 이용한풀이는 간결해 보이지만, 이중 포문을 통해 방문여부(visit)와 그림존재여부(board)를 조사하고 dfs함수를 호출하고, dfs함수 안에서 상하좌우 이동한 좌표가 if문 조건을 수행하면 다시 dfs함수를 재귀호출 해야 한다.

bfs를 이용한 풀이는  큐에 그림이 존재하는 영역의 좌표들을 푸쉬하고 각 구간마다의 영역의 넓이(cnt)를 벡터에 저장한다. 저장한 후 넓이(cnt)는 다시 1로 초기화 시켜줘야 한다.