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

 

 

문제 설명

A 회사의 물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다. 특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.

최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크레인을 사용하면 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 세로로 4줄, 가로로 5줄이 놓인 창고를 예로 들어보겠습니다. 이때 "A", "BB", "A" 순서대로 해당 종류의 컨테이너 출고 요청이 들어왔다고 가정하겠습니다. “A”처럼 알파벳 하나로만 출고 요청이 들어올 경우 지게차를 사용해 출고 요청이 들어온 순간 접근 가능한 컨테이너를 꺼냅니다. "BB"처럼 같은 알파벳이 두 번 반복된 경우는 크레인을 사용해 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 컨테이너가 꺼내져 3번의 출고 요청 이후 남은 컨테이너는 11개입니다. 두 번째 요청은 크레인을 활용해 모든 B 컨테이너를 꺼냈음을 유의해 주세요. 세 번째 요청이 들어왔을 때 2행 2열의 A 컨테이너만 접근이 가능하고 2행 3열의 A 컨테이너는 접근이 불가능했음을 유의해 주세요.

처음 물류창고에 놓인 컨테이너의 정보를 담은 1차원 문자열 배열 storage와 출고할 컨테이너의 종류와 출고방법을 요청 순서대로 담은 1차원 문자열 배열 requests가 매개변수로 주어집니다. 이때 모든 요청을 순서대로 완료한 후 남은 컨테이너의 수를 return 하도록 solution 함수를 완성해 주세요.

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

---

 

 

 

 

 

 

제한 사항

• 2 ≤ storage의 길이 = n ≤ 50
  • 2 ≤ storage[i]의 길이 = m ≤ 50
    • storage[i][j]는 위에서 부터 i + 1번째 행 j + 1번째 열에 놓인 컨테이너의 종류를 의미합니다.
    • storage[i][j]는 알파벳 대문자입니다.
• 1 ≤ requests의 길이 ≤ 100
  • 1 ≤ requests[i]의 길이 ≤ 2
  • requests[i]는 한 종류의 알파벳 대문자로 구성된 문자열입니다.
  • requests[i]의 길이가 1이면 지게차를 이용한 출고 요청을, 2이면 크레인을 이용한 출고 요청을 의미합니다.

---

 

 

 

 

 

 

풀이

문제를 요약하면, 지게차를 통해 두 가지 작업을 할 수 있고 모든 작업이 끝났을 때 남아있는 컨테이너의 개수를 구하면 된다.

두 가지 작업은 다음과 같다.

• 외부와 닿아 있는 컨테이너만 삭제
• 모든 컨테이너 삭제

 

두 번째 작업의 경우에는 모든 컨테이너를 살펴보며 해당하는 컨테이너만 지우면 되는 간단한 작업이다.

void PopAll(char target)
{
    for(int i = 0 ; i < Storage.size(); i++)
    {
        for(int j = 0;j < Storage[i].size(); j++)
        {
            if(Storage[i][j] == target)
            {
                Storage[i][j] = ' ';
            }
        }
    }
}

 

첫 번째 작업이 까다로운 이유는 외부와 접촉한 컨테이너인지 확인하는 작업과 예외 처리에 있다.

우선, 외부와 접촉한 컨테이너인지 확인하는 작업은 BFS를 통해 진행하였다.

목표 컨테이너를 시작으로 빈칸인 부분만을 큐에 넣으며 BFS를 진행하다 배열의 밖으로 나간다면 이는 외부와 접촉한 컨테이너임이 분명하다.

외부와 접촉한 컨테이너인지 확인하여 바로 지우면 예외가 발생할 수 있다.

해당 부분이 빈칸으로 바뀌어 다음 컨테이너가 판정할 때 영향이 생기기 때문이다.

따라서, 확인된 칸을 따로 저장하여 작업의 마지막에 일괄적으로 지워줘야 한다.

bool CheckOuter(int i, int j)
{
    queue<pair<int,int>> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    q.push({i,j});
    visited[i][j] = true;
    
    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();
        
        for(int i = 0 ; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];
            
            if(newY < 0 || newY >= n || newX < 0 || newX >= m)
            {
                 return true;
            }
            if(visited[newY][newX]) continue;
            if(Storage[newY][newX] != ' ') continue;
            
            visited[newY][newX] = true;
            q.push({newY, newX});
        }
    }
    
    return false;
}

void Pop(char target)
{
    vector<pair<int,int>> checked;
    
    for(int i = 0 ; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(Storage[i][j] == target)
            {
                if(CheckOuter(i, j))
                {
                    checked.push_back({i,j});
                }
            }
        }
    }
    
    for(auto& [i,j] : checked)
    {
        Storage[i][j] = ' ';
    }
}

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
vector<vector<char>> Storage;
int n, m;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

bool CheckOuter(int i, int j)
{
    queue<pair<int,int>> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    q.push({i,j});
    visited[i][j] = true;
    
    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();
        
        for(int i = 0 ; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];
            
            if(newY < 0 || newY >= n || newX < 0 || newX >= m)
            {
                 return true;
            }
            if(visited[newY][newX]) continue;
            if(Storage[newY][newX] != ' ') continue;
            
            visited[newY][newX] = true;
            q.push({newY, newX});
        }
    }
    
    return false;
}

void Pop(char target)
{
    vector<pair<int,int>> checked;
    
    for(int i = 0 ; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(Storage[i][j] == target)
            {
                if(CheckOuter(i, j))
                {
                    checked.push_back({i,j});
                }
            }
        }
    }
    
    for(auto& [i,j] : checked)
    {
        Storage[i][j] = ' ';
    }
}

void PopAll(char target)
{
    for(int i = 0 ; i < Storage.size(); i++)
    {
        for(int j = 0;j < Storage[i].size(); j++)
        {
            if(Storage[i][j] == target)
            {
                Storage[i][j] = ' ';
            }
        }
    }
}

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

---