[프로그래머스] Level 2. 지게차와 크레인

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

프로그래머스

 

 

뚫려있는 길을 어떻게 효율적으로 찾는지 문제이다.

 

storage에 대해, -는 비어있고 나가는길이 존재하는 칸 , ^는 비어있지만 나가는 길이 없는 칸을 의미한다. 모든 커맨드를 수행하면서 칸을 - 혹은 ^로 세팅한다. 

1. 만약 맵의 가장자리에 있거나, storage[i][j] 의 상하좌우중 뚫려있다는 의미의 '-' 가 하나라도 있다면, storage[i][j] 또한 '-'이다.
2. AA, BB 처럼 연속된 명령어가 나왔고, storage[i][j]가 (1)번의 경우에 해당되지 않으면(막혀있는 곳), '-' 대신 막혀있는 구멍을 의미하는 '^'를 넣는다. 이때, 발견되자마자 변경하는것이 아니라, 리스트로 검사를 모두 끝낸 후 한번에 바꿔야한다. 동일한 알파벳이 연달아 있을 경우, 안에있는 칸은 변경되면 안되기때문 (예제1의 세번째 request 참고)
3. 새로 '-'가 추가되었다면 ,  '^' 였던것이 뚫려서 '-'가 될수도 있으므로, 새로 추가되는 '-'에 대해 인접한 '^' 들을 모두 '-'로 변경하는 작업을 수행한다. -> check()함수. 이또한 모든 칸의 갱신작업이 끝난 뒤 수행해야한다.
4. 변경이 완료된 storage에 대해, '-'도 아니고 '^'도 아닌 칸의 개수를 반환한다.

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

using namespace std;

void check(vector<string>& storage, int i, int j){
    queue<pair<int,int>> q;
    q.push({i,j});
    while(!q.empty()){
        int x= q.front().first; int y= q.front().second;
        q.pop();
        storage[x][y]= '-';
        if(x>0 && storage[x-1][y]=='^')q.push({x-1,y});
        if(x<storage.size()-1 && storage[x+1][y] =='^') q.push({x+1,y});
        if(y>0 && storage[x][y-1] =='^') q.push({x,y-1});
        if(y<storage[x].size()-1 && storage[x][y+1]=='^')q.push({x,y+1});
    }
}
void pickup(vector<string>& storage, string cmd){
    char alpha = cmd[0]; bool inner = cmd.size() >1;
    
    
    //변경되어야 하는 칸 검사
    vector<pair<int,int>> list;
    for(int i=0; i<storage.size(); i++){
        for(int j=0; j<storage[i].size(); j++){
            if(storage[i][j] != alpha) continue;
            
            if(i==0|| i==storage.size()-1 || j ==0 || j== storage[i].size()-1) list.push_back(make_pair(i*100+j,'-'));
            else if(storage[i-1][j]=='-'||storage[i+1][j]=='-'||storage[i][j-1]=='-'||storage[i][j+1]=='-') list.push_back(make_pair(i*100+j,'-'));
            else if(inner) list.push_back(make_pair(i*100+j,'^'));
        }
    }
    
    //다적어
    for(int i = 0; i<list.size(); i++){
        int x= list[i].first/100; int y = list[i].first%100; 
        storage[x][y]= list[i].second;
    }
    
    //인접한 ^를 -로 변경하는 작업 
    for(int i = 0; i<list.size(); i++){
        int x= list[i].first/100; int y = list[i].first%100; 
        if(storage[x][y] == '-') check(storage, x,y);
    }   
}

int solution(vector<string> storage, vector<string> requests) {
    
    for(int i=0; i<requests.size(); i++) pickup(storage, requests[i]);
    
    
    int answer = 0;
    for(int i=0; i<storage.size(); i++){
        for(int j=0; j<storage[i].size(); j++){
            if(storage[i][j] != '-' && storage[i][j] != '^')answer++;
        }
    }
    
    return answer;
}