SW Expert Academy 2105. 디저트 카페

문제

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

걸린 시간

01 : 26 : 26

풀이

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define INF 987654321
using namespace std;

int n;
int dy[4] = {1, 1, -1, -1}; // ↘ ↙ ↖ ↗
int dx[4] = {1, -1, -1, 1};

int tour(int sy, int sx, int ey, int ex, vector<vector<int>>& cafe){
    int ret = -1;
    int y = sy;
    for(int x = sx+1; x < ex-1; x++){
        set<int> s;
        int ny = y;
        int nx = x;
        bool isValid = true;
        for(int i = 0; i < 4; i++){
            while(true){
                if(sy > ny+dy[i] || ey <= ny+dy[i] || sx > nx+dx[i] || ex <= nx+dx[i]) break;
                ny += dy[i];
                nx += dx[i];
                if(s.find(cafe[ny][nx]) == s.end())
                    s.insert(cafe[ny][nx]);
                else
                    isValid = false;
            }
        }
        int size = s.size();
        if(isValid) ret = max(ret, size);
    }
    return ret;
}

int solve(vector<vector<int>>& cafe){
    int ret = -1;
    for(int size = 3; size <= n; size++)
        for(int sy = 0; sy <= n-size; sy++)
            for(int sx = 0; sx <= n-size; sx++)
                ret = max(ret, tour(sy, sx, sy+size, sx+size, cafe));
    return ret;
}

int main()
{
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> n;
        vector<vector<int>> cafe(n, vector<int>(n, 0));
        for(int y = 0; y < n; y++)
            for(int x = 0; x < n; x++)
                cin >> cafe[y][x];
        cout << "#" << test_case << " " << solve(cafe) << "\n";
    }
    return 0;
}

대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아오는 모양은 직사각형 혹은 정사각형이지만, 크게보면 항상 커다란 정사각형 속에 존재한다. 제일 작은 정사각형(3x3)부터 제일 큰 정사각형(nxn)까지의 범위에서 가장자리를 포함한 사각형 모양의 카페 투어 경로들을 조사하면 모든 경우가 된다.