C++ / 1926 / 그림 ( 깊이 우선 탐색 )

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

문제 요약

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넒이가 가장 넒은 것의 넓이를 출력해야합니다.

단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의합니다.

가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림입니다. 그림의 넓이란 그림에 포함된 1의 개수 입니다.

문제 풀이

1. 도화지와 그림을 입력받습니다.

2. 그림의 개수를 세는 변수와 함수 내에서 그림의 넓이를 저장하는 변수, 가장 큰 넓이를 저장할 변수를 만듭니다.

3. dfs 함수를 만드는데 함수 내에서는 도화지 범위 안에서 상하좌우를 그림일 경우만 탐색합니다.

4. 탐색하면서 그림의 넓이를 저장합니다.

5. 탐색을 마쳤을때 그림의 개수를 세고 가장 큰 그림인지 넓이를 비교하여 저장합니다.

6. 그림의 개수와 가장 큰 그림의 넓이를 출력합니다.

주의할 점

탐색을 하면서 그림의 넓이를 저장하고 가장 큰 그림인지 확인하는 부분에서 변수 초기화를 잘 해주어야합니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

int n, m, sum = 0, refe = 0, cnt = 0;
bool visit[501][501];

vector<vector<int>> v;

void dfs(int x, int y)
{
	sum++;
	visit[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= n || nx < 0 || ny >= m || ny < 0)
		{
			continue;
		}
		if (v[nx][ny] == 0)
		{
			continue;
		}

		if (!visit[nx][ny])
		{
			visit[nx][ny] = true;
			dfs(nx, ny);
		}
	}
}

int main()
{
	cin >> n >> m;
	v.resize(n, vector<int>(m));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> v[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visit[i][j] && v[i][j] == 1)
			{
				dfs(i, j);
				// 큰 그림인지 비교 후 저장
				refe = max(sum, refe);
				sum = 0;
				cnt++;
			}
		}
	}

	cout << cnt << "\n" << refe;
	return 0;
}

반응형

예제

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

결과