[소프티어] Garage game (C++)

문제 링크: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=540 

Softeer

1. 주의할 점

- 시뮬레이션을 통해 구현한다

- 최대한 최적화를 진행해야 겨우 통과한다

- 같은 색의 차량 1대도 사라질 수 있다

 

2. 구현

- 3번의 DFS() 함수를 수행한다

- DFS() 함수내에는 다음과 같은 기능을 순차적으로 수행한다

- 현재 차량의 상태를 나타내는 Arr[][] 배열을 Dup[][] 배열에 저장한다

- Dup[][] 배열에서 차고에 해당하는 부분에 대해 BFS를 수행하여 같은 색의 차량을 구한다. 이때, 가장 minX,minY,maxX,maxY를 갱신하면서 구한다

- 차고에서 사라진 차를 위에서부터 내린다. 이때, Cnt==2라면 안내려도 되므로 생략한다 → TLE 피하는 방법

- 추가로, 차량을 내릴 때 minX,minY,maxX,maxY를 활용하여 내려야하는 곳만 내린다 → TLE 피하는 방법

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct info{
    int y,x;
};
int arr[45][15];
int num,answer=0;

void dfs(int cnt, int sum){
    bool check[15][15]={false,};
    int dup[45][15];
    //dup에 현재 arr상태 복사
    memcpy(dup,arr,sizeof(arr));
    for(int i=2*num;i<3*num;i++){
        for(int j=0;j<num;j++){
            int val = dup[i][j];
            if(val==0 || check[i-2*num][j]) continue;        //빈 경우, 이미 검사한 곳
            //초기화
            memcpy(arr,dup,sizeof(arr));
            int minX = j;
            int maxX = j;
            int minY = i;
            int maxY = i;
            queue<info> q;
            int same = 1;
            q.push({i,j});
            check[i-2*num][j]=true;
            while(!q.empty()){
                int cx = q.front().x;
                int cy = q.front().y;
                //빈 처리
                arr[cy][cx]=0;
                q.pop();
                minX = min(minX,cx);
                maxX = max(maxX,cx);
                minY = min(minY,cy);
                maxY = max(maxY,cy);
                for(int k=0;k<4;k++){
                    int nx = cx+dx[k];
                    int ny = cy+dy[k];
                    if(nx>=0 && ny>=2*num &&nx<num && ny<3*num && !check[ny-2*num][nx] && dup[ny][nx]==val){
                        check[ny-2*num][nx]=true;
                        q.push({ny,nx});
                        same++;
                    }
                }
            }
            if(cnt<2){   
                //아래로 내림
                for(int k=minX;k<=maxX;k++){
                    for(int m=maxY;m>=minY;m--){
                        if(arr[m][k]!=0) continue;
                        int jump=0;
                        //jump칸씩 내림
                        for(int l=m-1;l>=0;l--){
                            if(arr[l][k]){
                                jump=m-l;
                                break;
                            }
                        }
                        if(jump){
                            for(int l=m;l>=jump;l--){
                                arr[l][k]=arr[l-jump][k];
                                arr[l-jump][k]=0;
                            }
                        }
                    }
                }
                dfs(cnt+1,sum+same+(maxX-minX+1)*(maxY-minY+1));
            }
            else{
                answer = max(answer, sum+same+(maxX-minX+1)*(maxY-minY+1));
                continue;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>num;
    for(int i=0;i<3*num;i++)
        for(int j=0;j<num;j++)
            cin>>arr[i][j];
    dfs(0,0);
    cout<<answer;
    return 0;
}