[프로그래머스 2레벨] 지게차와 크레인 (C++)

#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

bool visited[51][51];

int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

void Lift(char target, vector<string>& storage, int n, int m)
{
    vector<pair<int, int>> del;
    memset(visited, false, sizeof(visited));
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(i!=0 && i!=n-1 && j!=0 && j!=m-1) continue; //가장 자리 체크
            if(storage[i][j] == target) del.push_back({i, j}); //삭제 대상
            else if(storage[i][j] == ' ') //근처 경계 탐색
            {
                queue<pair<int, int>>q;
                q.push({i, j});
                visited[i][j]=1;
                
                while(!q.empty())
                {
                    auto [x, y] = q.front();
                    q.pop();
                    
                    for(int k=0; k<4; k++)
                    {
                        int ny = y+dy[k];
                        int nx = x+dx[k];
                        
                        if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue;
                        if(storage[nx][ny]==target) //삭제 대상
                        {
                            del.push_back({nx, ny});
                            visited[nx][ny]=1;
                        }
                        
                        if(storage[nx][ny]==' ') //이어서 경계 탐색
                        {
                            q.push({nx, ny});
                            visited[nx][ny]=1;
                        }
                        
                    }
                }
            }
            
        }
    }
    
    for(auto i : del) //삭제 처리
    {
        storage[i.first][i.second] = ' ';
    }
}
    
void Crain(char target, vector<string>& storage, int n, int m)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(storage[i][j] == target) storage[i][j] = ' '; //삭제 처리
        }
    }
}

int solution(vector<string> storage, vector<string> requests) {
    int answer = 0;
    
    int n = storage.size();
    int m = storage[0].size();
    
    for(auto request : requests)
    {
        if(request.size()==1) Lift(request[0], storage, n, m);
        else Crain(request[0], storage, n, m);
    }
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(storage[i][j] != ' ') answer++;
        }
    }
    return answer;
}

 

주어진 requests 길이에 따라 지게차와 크레인 2가지 기능이 필요하므로, 각 기능에 대한 함수를 만들어준다.

우선 크레인의 경우 간단하게 바로 2중 반복문을 통해 target일 경우 모두 삭제해주면 된다.

이때 주의할 것은 삭제한 내용을 토대로 계속해서 탐색을 이어나가기에 참조를 통해 함수에 값을 넘겨주어야 한다.

 

지게차의 경우 우선 가장 자리만 체크한다는 것을 생각해야 한다.

가장 자리이외에는 전부 스킵하고, 가장 자리에 타겟 문자가 존재하면 좌표를 따로 저장해 삭제 대상에 추가해준다.

만약 빈칸이라면 가장 자리가 늘어나 추가로 삭제할수 있는 값이 생길 수 있다.

따라서 근처 경계를 추가적으로 탐색해야 한다.

이때 BFS를 써서 탐색하며, 마찬가지로 다음 좌표가 타겟이라면 삭제 대상에 추가해주며 빈칸이라면 큐에 다음 좌표를 넣고 근처 경계 탐색을 이어나간다.

 

이 과정을 통해 삭제 대상을 모두 찾고나서 삭제 처리를 해준다.

requests 값 전부에 대해 시행해주고 이제 빈칸이 아닌 값을 세서 출력해주면 된다.