그림의 개수와 가장 넓은 그림의 넓이를 출력하는 문제이다.(섬의 개수를 찾는 문제와 비슷함.)
이 문제는 가로나 세로로 연결된 것만 연결되어 있다고 본다.(대각선으로 연결되면 떨어진 그림임.)
특정한 지점을 선택한 후 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;
}
'백준 > 실랜디, 골랜디' 카테고리의 다른 글
[백준] C++ 문자열 폭발(9935) (0) | 2025.01.12 |
---|---|
[백준] C++ 탑(2493) (0) | 2025.01.10 |
[백준] C++ 스타트와 링크(14889) (0) | 2025.01.09 |
[백준] C++ 에디터(1406) (1) | 2025.01.09 |
[백준] 좋다(1253) (0) | 2025.01.08 |