[Softeer] Lv3.Garage Game

https://softeer.ai/practice/6276

최근에 푼 문제 중에 가장 재밌기도 했고 생각하면서 이렇게 문제 낼수도 있구나,,, 해서 벨로그에 정리해보려고함.

구현 문제인데 삼성 기출에서 많이 볼수 있는 떨어지고 올라가고 ,,,? 그런 문제랑 DFS 랑 섞은거 같다.

3번의 시뮬레이션만 돌리면 되니 또 한번의 시뮬레이션에 따라서 결과가 달라질수 있음으로 DFS 로 문제를 풀려고 했다.

어찌됐든 현재 있는 곳에서 자신의 4방향에 있는것들을 삭제하게 되고 그것이 또 다음시뮬레이션에 영향을 주게 된다.

그러면 N의 최대값인 15를 가정하고 15*15=625 가 한번의 시뮬레이션에 돌수있음으로 3번을 제곱하면 최대 2억,,,,의 결과가 나온다,,,,, 이건 1초를 훨씬 넘게 되니까 다른 방법으로 생각하려했다.

근데 결국 3번이니까 2번까지만 DFS를 돌리고 마지막은 BFS 한번만 돌리면 되는거 아닌가,,? 라는 생각이 들게 됐고 그럼 625*625+625가 되게된다.그럼 시간안에 들기도 했고 이렇게 구현하기로 한다.

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

using namespace std;

int answer;
int N;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int max_Ret[15];

pair<int, int> BFS_iter(vector<vector<int>>&arr,vector<vector<bool>>&visited, int x, int y, int num) {
    int dx, dy;
    int tempCnt = 0;
    
    int minX=x,minY=y;
    int maxX = x, maxY = y;
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y]=1;
    arr[x][y]=0;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        maxX = max(x, maxX); maxY = max(y, maxY);
        minX = min(x,minX); minY =min(y,minY);
        tempCnt += 1;
        q.pop();

        for (int i = 0; i < 4; i++) {
            dx = x + dir[i][0];
            dy = y + dir[i][1];

            if (dx < 0 or dx >= N or dy < 0 or dy >= N or visited[dx][dy] == 1 or arr[dx][dy]!=num) {
                continue;
            }

            visited[dx][dy] = 1;
            arr[dx][dy]=0;
            q.push({dx, dy});
        }
    }
//    cout << "# " <<  tempCnt << " " << minX << " " << minY << " " <<  maxX << " " << maxY << "\n";
//    cout << (maxX-minY+1) " " << (maxY-minY+1) << "\n";
    return {tempCnt, ((maxX-minX+1) * (maxY-minY+1))}; // cnt, size
}

void up_(vector<vector<int>> &arr) {
    for (int j = 0; j < N; j++) {
        int idx = 0;
        for (int i = 0; i < 3 * N; i++) {
            if (arr[i][j] != 0) {
                if (idx != i) {
                    swap(arr[idx][j], arr[i][j]);
                }
                idx++;
            }
        }
    }
}


void go_(vector<vector<int>> &arr,int cnt, int ret) {
    
//    cout << "# " << cnt << " " << ret << "\n";
//    display_(arr);
    
    if (cnt == 2) {
        int tempRet=0;
        vector<vector<bool>> visited(N, vector<bool>(N, 0));
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(visited[i][j]==0) {
                    pair<int,int> temp=BFS_iter(arr, visited, i, j, arr[i][j]);
                    tempRet=max(tempRet,temp.first+temp.second);
                    
                }
            }
        }
        answer=max(answer,ret+tempRet);
        return;
    }

    vector<vector<bool>> visited(N, vector<bool>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            vector<vector<int>> tempArr=arr;
            if (visited[i][j] == 0) {
                pair<int, int> temp = BFS_iter(tempArr,visited, i, j, tempArr[i][j]);
                up_(tempArr);
                go_(tempArr,cnt + 1, ret + (temp.first+temp.second));
            }
            tempArr=arr;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    vector<vector<int>> arr(3*N, vector<int>(N, 0));
    
    for (int i = 3 * N - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    go_(arr, 0, 0);
    
    cout << answer << "\n";

    return 0;
}

사실 이 코드를 그대로 작성하긴 했지만 이렇게 해도 시간 초과가 났었음,,,
그래서 vector size 줄이고 다른거 다 줄이고 최최최적화 하니까 통과가 되긴했음,,,
재밌게 푼 문제인 만큼 다음에는 좀더 최적화를 할수 있는 코드를 짜봐야겠다.