[C++] [2025 프로그래머스 코드챌린지 1차 예선] 3번 / 지게차와 크레인

 

 

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

프로그래머스

 

문제 3줄 요약

1. n x m 크기의 물류창고에 출고 방식은 지게차와 크레인 두 가지가 있다.

2. 지게차는 외부와 접근할 수 있는 경우 / 크레인은 어느 것이든 접근해서 꺼낼 수 있다.

3. 출고 요청이 끝나고 난 후, 남은 물류 컨테이너 수를 출력해라.

 

---

 

 

물류 창고 컨테이너 적재량(= n)은 최대 50,

컨테이너 길이(= m)의 최대 또한 50이다.

 

출고 요청은 최대 100개이며,

알파벳 한 개로 구성된 요청은 지게차,

알파벳 두 개로 구성된 요청은 크레인을 사용한 요청이다.

 

    int n = storage.size();
    int m = storage[0].size();
    
    for(string cmd : requests)
    {
        if(cmd.size()==1)
            gCar(cmd[0], storage, n, m);	// 지게차 사용
        else crain(cmd[0], storage, n, m);	// 크레인 사용
    }

 

따라서 위와 같이

명령에 따른 지게차 및 크레인 사용에 대한 함수 요청을 작성하였다.

 

비교적 구현이 쉬운

크레인 함수부터 작성해보자

 

---

 

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] = ' ';
        }
    }
}

 

컨테이너를 하나씩 돌며

출고 요청이었던 target과 같은 물류들은 전부 출고 처리한다.

 

지게차가 조금 까다로운데

지게차는 외부로부터 접근이 가능한 물류들만 출고시킬 수 있다.

 

코드부터 살펴보자

 

---

 

 

bool visited[51][51];

void gCar(char target, vector<string> &storage, int n, int m){
    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,1,0,-1};
    
    vector<pair<int, int>> delPoint;
    
    for(int idx=0; idx<n; idx++)
        fill(visited[idx], visited[idx]+m, false);
    
    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) delPoint.push_back(make_pair(i,j));
            else if(storage[i][j] == ' '){
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                visited[i][j] = true;

                while(!q.empty()){
                    pair<int, int> xy = q.front();
                    q.pop();
                    
                    int x = xy.first, y = xy.second;

                    for(int dir=0; dir<4; dir++){
                        int nx = x+dx[dir], ny = y+dy[dir];
                        if(nx<0 || nx>=n || ny<0 || ny>=m) continue;

                        if(storage[nx][ny]==target && !visited[nx][ny]) {
                            delPoint.push_back(make_pair(nx,ny));
                            visited[nx][ny] = true;
                        }
                        if(storage[nx][ny]==' ' && !visited[nx][ny])
                        {
                            q.push(make_pair(nx, ny));
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }
    }
    for(pair<int, int> point : delPoint)
        storage[point.first][point.second] = ' ';
}

 

테두리 범위를 탐색하며

target이 있다면 출고 처리한다.

 

만약 테두리에 빈 공간이 있다면

BFS를 통해 안쪽까지 살펴보며 갈 수 있는 선에서 target들을 출고 처리한다.

 

여기서 찾는 즉시 출고처리를 하면,

그만큼 빈공간이 생겨 BFS를 진행할 공간이 더 생기게 된다.

 

문제에서는

마치 마작 패 맞추기 게임처럼 외부만 한번씩 훑는게 지게차의 출고방식이므로

출고할 좌표들을 담아 놓고

탐색이 끝나면 일괄적으로 출고 처리를 해준다.

 

---

 

이후

모든 컨테이너를 살펴보며

남은 물류 개수를 카운트 해주면 되겠다.

 

정답 코드는 아래와 같다.

 

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

using namespace std;

bool visited[51][51];

void gCar(char target, vector<string> &storage, int n, int m){
    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,1,0,-1};
    
    vector<pair<int, int>> delPoint;
    
    for(int idx=0; idx<n; idx++)
        fill(visited[idx], visited[idx]+m, false);
    
    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) delPoint.push_back(make_pair(i,j));
            else if(storage[i][j] == ' '){
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                visited[i][j] = true;

                while(!q.empty()){
                    pair<int, int> xy = q.front();
                    q.pop();
                    
                    int x = xy.first, y = xy.second;

                    for(int dir=0; dir<4; dir++){
                        int nx = x+dx[dir], ny = y+dy[dir];
                        if(nx<0 || nx>=n || ny<0 || ny>=m) continue;

                        if(storage[nx][ny]==target && !visited[nx][ny]) {
                            delPoint.push_back(make_pair(nx,ny));
                            visited[nx][ny] = true;
                        }
                        if(storage[nx][ny]==' ' && !visited[nx][ny])
                        {
                            q.push(make_pair(nx, ny));
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }
    }
    for(pair<int, int> point : delPoint)
        storage[point.first][point.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(string cmd : requests)
    {
        if(cmd.size()==1)
            gCar(cmd[0], storage, n, m);
        else crain(cmd[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;
}

 

---

 

지게차 부분이 좀 까다로웠다.

알고리즘은 BFS 뿐이었지만,, 조건을 어떻게 해결 할지에서

헤맸던 문제였다..

 

끝!