[소프티어] 사물인식 최소 면적 산출 프로그램 / C++

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=531 

Softeer

공식 해설: https://softeer.ai/class/algotutor/detail.do?id=69 

Softeer

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

#define X first
#define Y second

#define ABS(x) (((x)<0) ? -(x) : (x))
using namespace std;

typedef pair<int, int> P;
vector<P> points[20];
int res = 2000 * 2000;
P p[20];
bool used[20][100] = {false, };
void f(int k, int n){
	if(k == n){
		int min_x = 1000, min_y = 1000;
		int max_x = -1000, max_y = -1000;
		for(int i = 0 ; i < n ; i ++){
			min_x = min(min_x, p[i].X);
			max_x = max(max_x, p[i].X);
			
			min_y = min(min_y, p[i].Y);
			max_y = max(max_y, p[i].Y);
		}
		int area = ABS(max_x - min_x) * ABS(max_y - min_y);
		res = min(area, res);

		return;
	}
	for(int i = 0 ; i < points[k].size() ; i ++){
		if(!used[k][i]){
			used[k][i] = true;
			p[k] = points[k][i];


			int min_x = 1000, min_y = 1000;
			int max_x = -1000, max_y = -1000;
			for(int i = 0 ; i <= k ; i ++){
				min_x = min(min_x, p[i].X);
				max_x = max(max_x, p[i].X);
				
				min_y = min(min_y, p[i].Y);
				max_y = max(max_y, p[i].Y);
			}

			int area = ABS(max_x - min_x) * ABS(max_y - min_y);
			if(area < res) f(k + 1, n);
			used[k][i] = false;
		}
	}

	
}
int main(int argc, char** argv)
{
	int n, k;
	cin >> n >> k;
	for(int i = 0 ; i < n ; i ++){
		int x, y, l;
		cin >> x >> y >> l;
		points[l-1].push_back({x, y});
	}
	f(0, k);
	cout << res;
	return 0;
}

 

풀이: DFS를 이용한 풀이

 

모든 색마다 하나씩의 점을 브루투포스 방법으로 순서쌍을 구한다. 그 순서쌍에서 최소 직사각형의 넓이는 그 순서쌍에 있는 x, y좌표의 최대 x, y좌표와 최소 x, y좌표의 넓이가 된다.

 

 

시간복잡도?

 

모든 순서쌍의 조합을 N (최대 100) 개와 K (최대 20개) 개의 조건에서 생각해보면 최악의 경우 연산은 같은 색깔이 5개씩 총 20개의 색이 존재하는 경우일 것이다. 이 경우 순서쌍을 추출하는 경우는 5 * 5 * 5  * ... * 5 로 5^20 정도의 연산을 한다. 꽤나 큰 숫자이기 때문에 중간에 조건을 만족못하는 순서쌍이 나올 경우 더이상 진행하지 않고 가지를 끊는게 좋은 방법이라고 생각하였다.

 

여기서 시간을 줄일 수 있는 방법을 살펴보자면 순서쌍을 구하면서 n개까지 k가 올라가는 과정에서 최소 직사각형의 넓이를 구해보고 이전에 기록된 넓이보다 크면 점의 갯수가 늘으면 커질 수는 있지만 작아질 수는 없기때문에 최소값이 절대 되지 못한다. 그러므로 더 이상 진행하지 않고 다음 케이스의 순서쌍을 구하는 작업을 하였다.

 

 

공식해설의 두번째 풀이법을 이용한 코드로 리뷰해볼 예정이다.