[C++] 소프티어: [인증평가(2차) 기출] Garage game (시간 초과)

🔗 문제

https://softeer.ai/practice/info.do?idx=1&eid=540&sw_prbl_sbms_sn=158428

Softeer

백준 뿌요뿌요같은 문제인데 아직 시간초과를 해결하지 못 했다.

알고리즘 단톡방에 올렸는데 아무도 대답해주지 않았고 (…)

나처럼 풀었는데 성공한 사람은 꼭 알려주면 좋겠다.

꼭!

 

 

🖍 풀이

 

• N*N 구역에서 같은 색깔의 위치로 면적과 몇 대가 있는지 구해야 한다.
  • N*N 구역에서 사라질 수 있는 차량 종류는 여러 가지이므로 DFS를 사용한다.

 

• 같은 색깔이 주변에 있는지 탐색하는 것은 BFS를 사용한다.
  • 같은 종류의 차량이 있는 면적을 구해야 하기 때문에 최대 및 최소 좌표와 같은 차량의 개수를 갱신해준다.

 

• 같은 종류의 차종을 맵에서 지운 후, 아래로 끌어 내려야 한다.

 

DFS를 사용하여, 깊이가 3이 될 때까지 반복하여 정답을 출력한다.

 

 

정말 뭐가 잘못됐는지 모르겠다.

 

💾  소스

#include <iostream>
#include <queue>
#include <memory.h>

typedef std::pair<int, int> pii;

const int INF = 987654321;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int N, answer = 0;
int map[45][15] = {0, };

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=N)
        return false;
    
    return true;
}


void DFS(int depth, int score)
{
    if(depth == 3)
    {
        answer = (answer > score ? answer : score);
        return;
    }
    
    int origin[45][15];
    memcpy(origin, map, sizeof(origin));
    
    bool visited[45][15] = {false, };
    
    
    for(int r=0; r<N; ++r)
    {
        for(int c=0; c<N; ++c)
        {
            
            if(map[r][c] == 0 || visited[r][c])
                continue;

            memcpy(map, origin, sizeof(origin)); // init
            map[r][c] = 0;
            
            std::queue<pii> q;
            q.push({r, c});
            
            visited[r][c] = true;
            int cnt = 1;
            int area = 0;
            
            int maxX = r, minX = r;
            int maxY = c, minY = c;
            
            // find_same() 같은 색깔 찾기
            while(!q.empty())
            {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();

                for(int d=0; d<4; ++d)
                {
                    int nowX = dx[d] + x;
                    int nowY = dy[d] + y;
                    
                    if(!isValid(nowX, nowY) || visited[nowX][nowY] || origin[x][y] != map[nowX][nowY])
                        continue;
                    
                    
                    map[nowX][nowY] = 0;
                    visited[nowX][nowY] = true;

                    q.push({nowX, nowY});
                    
                    cnt++;
                    
                    if(nowX > maxX) maxX = nowX;
                    if(nowX < minX) minX = nowX;
                    if(nowY > maxY) maxY = nowY;
                    if(nowY < minY) minY = nowY;
                    
                }
            }
            
            // replace
            for(int i=0; i<N; ++i)
            {
                int idx = 0;
                for(int j=0; j<N*3; ++j)
                {
                    if(map[j][i] != 0)
                    {
                        map[idx++][i] = map[j][i];
                    }
                }
            }

            DFS(depth + 1, score + ((maxX-minX+1) * (maxY-minY+1)) + cnt);
        }
    }

}

int main()
{
    
    std::cin >> N;
    // 편의를 위해 역순으로 받음
    for(int i=N*3-1; i>=0; --i)
    {
        for(int j=0; j<N; ++j)
            std::cin >> map[i][j];
    }

    DFS(0, 0);
    
    std::cout << answer;
    
    return 0;
}