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

https://school.programmers.co.kr/learn/courses/30/lessons/388353

프로그래머스

 

 

생각 흐름

• 입력이 100, 50, 50으로 최대로 계산했을 때 250000 밖에 안 되는 것을 파악.
• 1초안에 성공하려면 400회의 이내로 연산이 진행되어야 함을 파악.
• size 2일 때는 추가 연산 과정 없이 바로 없애주면 되므로 문제 안 됨.
• size 1일 때 bfs를 통해 외부와 닿아있는 것들을 저장하는 방식으로 결정. 이 때 외부와 닿아있다고 바로 제거해주면 안 됨.

 

 

#include <string>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int moveX[4] = {0,0,1,-1};
int moveY[4] = {1,-1,0,0};

bool validateEdge(int y, int x, vector<string> storage){
    queue<pair<int, int>> q;
    q.emplace(y,x);
    bool checked[50][50];
    memset(checked, false, sizeof(checked));
    while(!q.empty()){
        pair<int, int> node = q.front();
        q.pop();
        if(node.first<0 || node.first>=storage.size() || node.second<0 || node.second>=storage[0].size()){
            return true;
        }
        if(storage[node.first][node.second]!=0 || checked[node.first][node.second]){
            if(node.first==y && node.second == x){
                
            }else{
                continue;
            }
        }
        
        checked[node.first][node.second] = true;
        
        for(int i = 0; i<4; i++){
            int movedX = node.second+moveX[i];
            int movedY = node.first+moveY[i];
            q.emplace(movedY, movedX);
        }
    }
    
    return false;
}

int solution(vector<string> storage, vector<string> requests) {
    int answer = 0;
    
    for(int i = 0; i<requests.size(); i++){
        vector<pair<int,int>> v;
        for(int j = 0; j<storage.size(); j++){
            for(int k = 0; k<storage[j].size(); k++){
                if(storage[j][k]==requests[i][0]){
                    if(requests[i].size()==1){
                        if(validateEdge(j, k, storage)) {
                            v.emplace_back(j,k);
                        }
                    }else{
                        storage[j][k]=0;
                    }
                }
            }
        }
        for(auto tmp : v){
            storage[tmp.first][tmp.second] = 0;
        }
    }
    
    for(int j = 0; j<storage.size(); j++){
        for(int k = 0; k<storage[j].size(); k++){
            if(storage[j][k]!=0){
                answer++;
            }
        }
    }
    
    return answer;
}