[C++/PGS] Lv.2 : 지게차와 크레인

 

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

프로그래머스

---

프로그래머스 레벨 2

2025 프로그래머스 코드 챌린지 1차 예선 문제 - 정답률 42%...

꽤 복잡한 구현+그래프 탐색 문제이다.

 

이 문제의 포인트는 bfs 뿐만아니라, 뺄 수 있는 짐을 어느 루트로 어떻게 탐색할지 찾는게 중요함‼️

 

예를 들어서, 명령어가 "A"일 때

나는 처음에 'A'라는 짐을 찾고, 이 짐에서 시작하여 모서리까지 도달할 때까지 상하좌우로 탐색했는데

이게 아니라 모서리의 빈칸에서 bfs로 'A'까지 도달해야 해결되는 문제였다 ㅠㅠ

Store에서 for문을 돌리며

모서리에 있는 문자가 'A'이면 -> 이 좌표를 바로 저장하고,

모서리가 빈칸이면 -> 여기서부터 안쪽으로 탐색하며 'A'를 찾기

그리고 visited 처리도 중요하다!!

 

삽질하느라 고생했는데 🥹 이 글이 누군가에게 도움이 되길..!

참고로 코드에서 map은 안 써도 된다 (삽질의 흔적)

 

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

vector<string> Store;
int n; int m;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int visited[51][51] ={0,};
int visitId = 1;
unordered_map<char, vector<pair<int, int>>> letters;

void deleteBox(string req){
    char r = req[0];
    if(req.length()==2){
        for(auto p: letters[r]){
            Store[p.first][p.second] = ' ';
        }
        letters[r].clear();
        return;
    }
    vector<pair<int, int>> box;
    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(Store[i][j]==r) {
                box.push_back({i,j});
                continue;
            }
            // 빈칸이어야 함
            if(Store[i][j]!=' ') continue;
            queue<pair<int,int>> q;
            q.push({i,j});
            visited[i][j] = visitId;
            while(!q.empty()){ // 빈칸에서 bfs로 r을 찾기
                auto [a, b] = q.front();
                q.pop();
                for(int k=0; k<4; ++k){
                    int nx = a+dx[k];
                    int ny = b+dy[k];
                    if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
                    if(visited[nx][ny]==visitId) continue;
                    // 다음 칸이 r인 경우 - box에 저장
                    if(Store[nx][ny]==r){
                        box.push_back({nx,ny});
                        visited[nx][ny] = visitId;
                    }
                    // 다음 칸도 빈칸이면 계속 탐색
                    if(Store[nx][ny]==' '){
                        q.push({nx,ny});
                        visited[nx][ny] = visitId;
                    }
                }
            }
        }
    }
    visitId++;
    for(auto b: box) Store[b.first][b.second] = ' ';
}

int solution(vector<string> storage, vector<string> requests) {
    int answer = 0;
    Store = storage;
    n = storage.size();
    m = storage[0].size();
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            char c = Store[i][j];
            letters[c].emplace_back(i, j);
        }
    }
    for(string req: requests){
        deleteBox(req);
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(Store[i][j]!=' ') answer ++;
        }
    }
    return answer;
}