소프티어 [HSAT 2회 인증평가 기출] 사물인식 최소 면적 산출 프로그램 (C++)

문제) https://softeer.ai/practice/6277

 

풀이)

dfs 를 이용한 백트래킹으로 모든 경우를 탐색하는 브루트포스를 사용했다.

각 색깔의 점을 하나씩 뽑아서 모든 점을 포함하는 사각형의 넓이 size를 만든다.

만약  size가 answer보다 크다면 그 루트는 이미 틀렸기 때문에 return 한다.(그냥 모든 경우 loop시 시간초과)

#include <bits/stdc++.h>
using namespace std;
int N, K;
int answer = 4000001;
vector <pair<int,int>> v[21];
vector <int> ans_x;
vector <int> ans_y;




void dfs(int k){
    if(k!=1) {
        int max_x = *max_element(ans_x.begin(), ans_x.end());
        int max_y = *max_element(ans_y.begin(), ans_y.end());
        int min_x = *min_element(ans_x.begin(), ans_x.end());
        int min_y = *min_element(ans_y.begin(), ans_y.end());
        int size = (max_x - min_x) * (max_y - min_y);
        if (k == K + 1) {
            if (answer > size)
                answer = size;
            return;
        }
        if (answer <= size) return;
    }
    for(int i = 0; i < v[k].size(); i++) {
        ans_x.push_back(v[k][i].first);
        ans_y.push_back(v[k][i].second);
        dfs(k + 1);
        ans_x.pop_back();
        ans_y.pop_back();
    }
}


int main(){
    cin >> N >> K;
    int x, y, k;
    for (int i = 0; i < N; ++i) {
        cin >> x >> y >> k;
        v[k].push_back({x,y});
    }


    dfs(1);
    cout << answer;

}

 

시간초과 났던 코드

#include <bits/stdc++.h>
using namespace std;
int N, K;
//점의 갯수, 색의 갯수
int answer = 4000001;
vector <pair<int,int>> v[21];
vector <pair<int,int>> ans;



void dfs(int k){
    if(k == K+1)
    {

        int max_x = -1001;
        int max_y = -1001;
        int min_x = 1001;
        int min_y = 1001;
        for(int i = 0; i < ans.size();i++){

            max_x = max({ans[i].first, max_x});
            max_y = max({ans[i].second, max_y});
            min_x = min({ans[i].first, min_x});
            min_y = min({ans[i].second, min_y});
        }
        int size = (max_x - min_x) * (max_y - min_y);
        if(answer > size)
            answer = size;
        return;
    }

    for(int i = 0; i < v[k].size(); i++) {
        ans.push_back({v[k][i].first,v[k][i].second});
        dfs(k + 1);
        ans.pop_back();
    }
}


int main(){
    cin >> N >> K;
    int x, y, k;
    for (int i = 0; i < N; ++i) {
        cin >> x >> y >> k;
        v[k].push_back({x,y});
    }


    dfs(1);
    cout << answer;

}

 

ps. 다음주가 hsat인데...