[C++]위클리 챌린지 아이템 줍기(프로그래머스 3레벨)

#include <string>
#include <vector>
#include <queue>
using namespace std;
 
// 위, 아래, 오른쪽, 왼쪽 계산용도
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };
 
int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY)
{
    // 좌표를 모두 2배 ( 이런 형식으로 )
    //  1 1      1 1 1
    //  1 1  ->  0 0 1
    //           1 1 1
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
 
    vector<vector<int>> vecRec(101, vector<int>(101, 0));
 
    // 직사각형의 시작점과 끝점
    int iXFirst = 0;
    int iXSecond = 0;
    int iYFirst = 0;
    int iYSecond = 0;
 
    for (int i = 0; i < rectangle.size(); ++i)
    {
        for (int j = 0; j < rectangle[0].size(); ++j)
        {
            // 내부 크기도 *2
            rectangle[i][j] *= 2;
        }
 
        iXFirst = rectangle[i][0];
        iYFirst = rectangle[i][1];
        iXSecond = rectangle[i][2];
        iYSecond = rectangle[i][3];
 
        for (int z = iYFirst; z <= iYSecond; ++z)
        {
            for (int k = iXFirst; k <= iXSecond; ++k)
            {
                vecRec[z][k] = 1;
            }
        }
    }
 
    // 직사각형의 내부 모두 0
    for (int i = 0; i < rectangle.size(); ++i)
    {
        iXFirst = rectangle[i][0];
        iYFirst = rectangle[i][1];
        iXSecond = rectangle[i][2];
        iYSecond = rectangle[i][3];
 
        for (int j = iYFirst + 1; j < iYSecond; ++j)
        {
            for (int z = iXFirst + 1; z < iXSecond; ++z)
            {
                vecRec[j][z] = 0;
            }
        }
    }
 
    // BFS
    queue<pair<int, int>> que = {};
    que.emplace(characterX,characterY);
 
    while (!que.empty())
    {
        int iX = que.front().first;
        int iY = que.front().second;
        que.pop();
 
        if (iX == itemX && iY == itemY)
            break;
 
        for (int i = 0; i < 4; ++i)
        {
            int iNextY = iY + dy[i];
            int iNextX = iX + dx[i];
 
            // 계산하지 않은 것만 1로
            if (vecRec[iNextY][iNextX] == 1)
            {
                que.emplace(iNextX, iNextY);
 
                // DP처럼 계산해나가면서 입력
                vecRec[iNextY][iNextX] = vecRec[iY][iX] + 1;
            }
        }
    }
 
    return  vecRec[itemY][itemX] * 0.5;
}
 

1.*2 한다는 생각을 하지 못했다.

2. BFS인거는 생각했는데 직사각형 내부를 어떻게 지우지...? 라는 생각만 가득했다

 

이걸 생각해내는 게 이 문제의 핵심이었는 듯