[백준] 그림(1926)

그림의 개수와 가장 넓은 그림의 넓이를 출력하는 문제이다.(섬의 개수를 찾는 문제와 비슷함.)

이 문제는 가로나 세로로 연결된 것만 연결되어 있다고 본다.(대각선으로 연결되면 떨어진 그림임.)

특정한 지점을 선택한 후 DFS나 BFS로 탐색을 하고 방문 여부를 체크해줘야 한다.(중복 방문을 회피)

나는 이 문제를 DFS로 해결하였다.

 

문제해결방법

1. (0,0)부터 (n-1, m-1)까지 모든 경우를 탐색하는데 방문되어 있지 않은 곳만 탐색한다.

2. 탐색을 시작하면 동서남북 방향으로 DFS로 탐색을 시작한다.(탐색을 한 곳은 visited를 1로 바꿔야 함)

3. 탐색을 할 때마다 넓이를 1씩 더해준다.(DFS로 탐색하기 때문에 사람이 바구니에 공을 하나씩 집어넣는다고 생각하면 편함.)

#include <iostream>
#include <vector>
using namespace std;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
vector<int> v[1000];
int visited[501][501];

int DFS(int x, int y,int num);
int n = 0;
int m = 0;
int main(void)
{
	cin >> n >> m;

	int num = 0;
	int max = 0;
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> num;
			v[i].push_back(num);
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (visited[i][j] == 0&&v[i][j]==1)
			{
				visited[i][j] = 1;
				int result=DFS(i,j,1);
				count++;
				if (result > max)
				{
					max = result;
				}
			}
		}
	}
	cout << count << endl;
	cout << max;
	
	return 0;
}

int DFS(int x, int y, int num)
{
	for (int i = 0; i < 4; i++)
	{
		if (x + dx[i] > -1 && y + dy[i] > -1 && x + dx[i] < n && y + dy[i] < m&&visited[x+dx[i]][y+dy[i]]==0&& v[x+dx[i]][y+dy[i]] == 1)
		{
			visited[x + dx[i]][y + dy[i]] = 1;
			num = DFS(x + dx[i], y + dy[i], num + 1);
		}
	}
	return num;
}