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

접근법:

요청에 따라서 지게차를 쓸지 크레인을 쓸지 결정한다.
1. 지게차를 쓸경우 대상이 외부에서 접근이 가능해야한다.
2. 크레인을 쓸경우 어떤 위치이던간에 접근이 가능하다.
지게차의 경우 현재 칸이 외부에서 접근 가능한지 판별한다.
1. 상하좌우를 살펴보고 창고의 경계선인지 확인한다. 경계선이라면 외부에서 접근 가능하다.
2. 만약에 상하좌우가 바로 외부가아니라 창고의 비어있는 칸이라면 그 칸에 대하여 경계선여부를 판단한다.
3. 이를 반복적으로 수행하여 결정한다.
이때, 배열에 순차적으로 접근하기때문에 순차적으로 접근하여 바로 문자를 없애면 외부와 통하는 길이 생길 수 도 있다.
1. 그래서 배열에 저장한뒤 탐색이 끝난뒤 조건에 해당하는 컨테이너만 없앤다.

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

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool canPull(int x, int y, int n, int m, const vector<string>& storage, vector<vector<bool>>& visited)
{
    visited[x][y] = true;
    for(int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m)
        {
            return true;
        } else if(storage[nx][ny] == '.' && !visited[nx][ny])
        {
            if(canPull(nx, ny, n, m, storage, visited))
                return true;
        }
    }
    return false;
}

int solution(vector<string> storage, vector<string> requests) {
    int answer = 0;
    int n = storage.size();
    int m = storage[0].size();
    int r = requests.size();
    for(int i = 0; i < r; ++i)
    {
        char request = requests[i][0];
        if(requests[i].size() == 1)
        {
            vector<pair<int, int>> canPullList;
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < m; ++j)
                {
                    if(storage[i][j] == request)
                    {
                        vector<vector<bool>> visited(n, vector<bool>(m, false));
                        if(canPull(i, j, n, m, storage, visited))
                        {
                            canPullList.push_back({i, j});
                        }
                    }
                }
            }
            for(int i = 0; i < canPullList.size(); ++i)
            {
                storage[canPullList[i].first][canPullList[i].second] = '.';
            }
        } 
        else 
        {
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < m; ++j)
                {
                    if(storage[i][j] == request)
                    {
                        storage[i][j] = '.';
                    }
                }
             }
        }
    }
    
    
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(storage[i][j] != '.')
            {
//                cout << storage[i][j];
                answer++;
            }
        }
//        cout << endl;
    }
                    
    
    return answer;
}

퍼즐 게임 챌린지[프로그래머스]

비밀 코드 해독[프로그래머스]