개요

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

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

접근 방식

1. 도화지를 순회하며 1인 칸이 존재하면 dfs를 통해 해당 그림이 몇 칸인지 확인했다.

int DFS(int x,int y,int N, int M)
{
	int sum = 1;
	visited[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int nextX = x + dirX[i];
		int nextY = y + dirY[i];

		if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
		{
			continue;
		}
		if (visited[nextX][nextY]) continue;
		if (board[nextX][nextY] == 0) continue;
			
		sum+= DFS(nextX, nextY, N, M);
	}
	return sum;
}

전체 코드

#include <string>
#include <vector>
#include<queue>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int dirX[4] = { 0,0,-1,1 };
int dirY[4] = { -1,1,0,0 };
int board[502][502];
bool visited[502][502];

int DFS(int x,int y,int N, int M)
{
	int sum = 1;
	visited[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int nextX = x + dirX[i];
		int nextY = y + dirY[i];

		if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
		{
			continue;
		}
		if (visited[nextX][nextY]) continue;
		if (board[nextX][nextY] == 0) continue;
			
		sum+= DFS(nextX, nextY, N, M);
	}
	return sum;
}

int main()
{
	int N, M, paintingCount=0, largestPainting=0;
	cin >> N >> M;


	for (int i = 0; i< N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}
	fill(&visited[0][0], &visited[501][502], false);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] == 1 && !visited[i][j])
			{
				paintingCount++;
				int paintSize= DFS(i, j,N,M);
				largestPainting = largestPainting > paintSize ? largestPainting : paintSize;
			}
		}
	}
	cout << paintingCount << endl;
    //0이면 0호출
	if (paintingCount == 0)
		cout << 0;
	else
		cout << largestPainting;
}