[SWEA_모의SW역량테스트] 2105번 - 디저트 카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

SW Expert Academy

SWEA 삼성 SW 역량테스트 모의 문제다.

이 문제는 작년 실제 기출 문제 '게리맨더링2(https://cpp-dev.tistory.com/51?category=852516)' 문제와 매우 유사하다. 하지만 그 문제보다는 처리할 코드가 적어 보다 쉽게 풀 수 있는 문제다.

 

이 문제는 시작점의 범위와 길이 1, 길이 2의 조합에 대해 그릴 수 있는 경우 해당 경로의 디저트 수를 구하는 완전탐색 문제다. 시뮬레이션 느낌도 좀 있다.

 

isPossible 함수는 주어진 시작점과 총 Map의 한 변의 길이, 그리고 길이 두 개가 주어졌을 때, 그 경로가 갈 수 있는 것인지 판별하는 함수다. 이 함수에서 true가 반환되면 해당 경로는 존재할 수 있는 것이므로, 경로를 따라가면서 디저트의 수를 구한 뒤, 중복이 없는지 조건을 따져 중복이 없다면 답을 갱신해준다.

 

아래는 소스코드. 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int T, N;
 
bool isPossible(int r, int c, int len1, int len2, int N){
    if ((0 <= (r - 1 + len1) && (r - 1 + len1) < N && (c + 1 - len1) >= 0 && (c + 1 - len1) < N) &&
        (0 <= (r + len1 + len2 - 2) && (r + len1 + len2 - 2) < N && 0 <= (c - len1 + len2) && (c - len1 + len2) < N) &&
        (0 <= (r + len2 - 1) && (r + len2 - 1) < N && 0 <= (c + len2 - 1) && (c + len2 - 1) < N)){
        return true;
    }
    return false;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    for (int tc = 1; tc <= T; tc++){
        int answer = -1;
        cin >> N;
        vector<vector<int> > Map;
        Map.assign(N, vector<int>(N, 0));
        for (int r = 0; r < N; r++){
            for (int c = 0; c < N; c++){
                cin >> Map[r][c];
            }
        }
        for (int r = 0; r < N-2; r++){
            for (int c = 1; c < N; c++){
                for (int len1 = 2; len1 < N; len1++){
                    for (int len2 = 2; len2 < N; len2++){
                        if (!isPossible(r, c, len1, len2, N)) continue;
                        else{
                            vector<int> disserts;
                            int curr = r;
                            int curc = c;
                            for (int i = 1; i < len1; i++){
                                disserts.push_back(Map[curr + 1][curc - 1]);
                                curr++;
                                curc--;
                            }
                            for (int i = 1; i < len2; i++){
                                disserts.push_back(Map[curr + 1][curc + 1]);
                                curr++;
                                curc++;
                            }
                            for (int i = 1; i < len1; i++){
                                disserts.push_back(Map[curr - 1][curc + 1]);
                                curr--;
                                curc++;
                            }
                            for (int i = 1; i < len2; i++){
                                disserts.push_back(Map[curr - 1][curc - 1]);
                                curr--;
                                curc--;
                            }
                            //cout << curr << " " << curc << '\n';
                            int tot_category = disserts.size();
                            sort(disserts.begin(), disserts.end());
                            disserts.erase(unique(disserts.begin(), disserts.end()), disserts.end());
                            int erased_ = disserts.size();
                            if (tot_category == erased_){ // 중복 없다면
                                answer = max(answer, tot_category);
                            }
                        }
                    }
                }
            }
        }
        cout << "#" << tc << " " << answer << '\n';
    }
    return 0;
}