C++ / 2583 / 영역 구하기 ( 깊이 우선 탐색 )

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

문제 요약

눈금의 간격이 1인 m * n 크기의 모눈종이가 있습니다.

눈금에 맞추어 k개의 직사각형을그릴 때, 이들 k개의 직사각형의 내부를 제외한 나머지 부분이 몇개의 분리된 영역으로 나누어 집니다.

m, n, k 그리고 k개의 직사각형의 좌표가 주어질 때, k개의 직사각형 내부를 제외한 나머지 부분이 몇개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을작성해야 합니다.

 

첫째 줄엔 m , n, k가 순서대로 주어지고

둘째 줄엔 k개의 직사각형의 사이즈가 주어집니다 

ex ) 0,2 * 4,4  사이즈의 직사각형 ( 이 입력받는 부분이 처음 봤을 때 헷갈렸습니다. )

문제 풀이

1. 입력받은 사이즈로 0으로 채워진 2차원 배열 모눈종이를 그립니다.

2. 사각형을 모눈종이에 그려야 합니다.

사각형 개수만큼 반복하는데, 사각형의 좌표는 시작x, 시작y, 끝x, 끝y 4개를 받아야합니다.

입력을 받고 나면 사각형 사이즈  안에 있을 때만 ( 사각형 넓이 일때 )  1을 더해줍니다. ( 사각형 그리기 )

그리고 나머지 사각형도 똑같이 반복합니다.

3. dfs함수를 만드는데 사각형이 아닌경우 ( 사각형은 1씩 더해주었기 때문에 사각형은 0이 아님 ), 모눈종이 사이즈를 넘어가는 경우를 제외하고 4방향으로 이어진 부분을 탐색해서 개수를 셉니다.

4. 0, 0 부터 n-1, m-1까지 방문하지 않은 노드이고, 사각형이 아닐때 dfs함수를 돌려 세어진 빈칸 개수를 정답 벡터에 저장합니다. ( 개수를 세는  sum변수는 항상 초기화 해주어야 함 )

5. 정답 벡터의 사이즈를 출력하고 ( 빈칸 영역의 개수 ) 벡터를 정렬하여 출력합니다.

주의할 점

이 문제에 예시로 주어진 모눈종이는 시작부분 ( 0, 0 )을 기준으로 끝나는 부분 ( n - 1, m - 1)이 기존 배열을 왼쪽으로 90도 돌린  상태입니다.

 

그림 예시

						n-1, m-1
0,0

 

기존에 사용하던 배열

0,0
				n-1,m-1

헷갈리지 않도록 주의해야합니다.

 

사각형을 그리는 로직을 만들때 3차원 배열로 하면 시간복잡도가 높아 시간 초과가 나올 것 같아서 고민하느라 시간이 걸렸던것 같습니다.

하지만 제출하기 전까지는 시간초과일지 정답일지 모른다고 생각이 들어서

일단 3차원 배열로 만들어 보고 제출하였는데 "맞았습니다!" 가 떠서 조금 당황했던 것 같습니다.

다음에 다시 이 문제를 풀게된다면 더 적은 비용으로 풀어보고 싶습니다.  

코드

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

using namespace std;

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

vector<vector<int>>v;
bool visit[100][100];
int m, n, k, sum = 0, cnt = 0;
vector<vector<int>> v2;

vector<int> v3;

void dfs(int  x, int y)
{
	visit[x][y] = true;
	// 빈칸 갯수
	sum++;
	for (int i = 0; i < 4; i++)
	{
		int nx = dx[i] + x;
		int ny = dy[i] + y;

		// 모눈종이 사이즈를 벗어난 경우
		if (nx >= n || nx <0 || ny >= m || ny < 0)
		{
			continue;
		}

		// 사각형이 있을경우
		if (v[nx][ny] != 0)
		{
			continue;
		}

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


int main()
{

	cin >> m >> n >> k;


	// 0으로 모눈종이 만들기
	v.resize(n, vector<int>(m));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			v[i][j] = 0;
		}
	}


	// 사각형 그리기
	v2.resize(k, vector < int> (4));
	for (int i = 0; i < k; i++)
	{
		// 사각형 사이즈 받기
		for (int j = 0; j < 4; j++)
		{
			cin >> v2[i][j];
		}

		// 받은 사각형 사이즈만큼 모눈 종이에 그리기
		for (int k = 0; k < n; k++)
		{
			for (int l = 0; l < m; l++)
			{
				// 입력 받은 사각형 사이즈안에 있을경우에만 1을 더해줌
				if (k >= v2[i][0] && k < v2[i][2] && l >= v2[i][1] && l < v2[i][3])
				{
					v[k][l] += 1;
				}
			}
		}
	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// 사각형이 없는 칸만 탐색
			if (!visit[i][j] && v[i][j] == 0)
			{
				dfs(i, j);
				v3.push_back(sum);
				// 다음 영역 탐색을 위해 초기화
				sum = 0;

			}
		}

	}

	// 빈칸 영역 갯수
	cout << v3.size()<< "\n";

	// 정렬
	sort(v3.begin(), v3.end());
	for (int i = 0; i < v3.size(); i++)
	{
		cout << v3[i] << " ";
	}

	return 0;
}

반응형

예제

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

결과