[프로그래머스/C++] 아이템 줍기

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

​

이 문제는 겹친 사각형으로는 캐릭터가 이동할 수 없다는게 핵심이다. 그래서 겹친 사각형의 경로를 없애주고, 없앤 다음 만들어진 경로를 BFS로 탐색하면 쉽게 풀리는 문제다.

 

BFS로 탐색하는 것은 쉽지만, 어떤 경로를 이동할 수 있는지를 구하는게 생각보다 어려웠다.

처음에는 사각형의 좌표를 기준으로 겹쳐있는지를 보고 겹친 부분을 조건에 따라 삭제하려고 했다.

 

하지만 코드가 생각보다 길어질 것 같아서, 잘 생각해보니 겹칠 경우는 조건을 잡을 필요없이 겹친 부분을 0으로 없애면 실제로 가능한 경로만 남게 된다는 사실을 알았다.

 

그래서 하나의 사각형에서 이동이 가능한 경로를 그리고, 그 사각형의 경로 위에 다른 사각형의 범위를 전부 0으로 없애 주었다. 그러면 실제로 사각형으로 경로를 그렸을 때 이동이 가능한 경우만 남게 된다.

 

문제는 주어진 범위를 그대로 사용했더니 실제로는 ㄷ자로 이동해야하는 경로가 [[1,1],[1,1]]로 표시가 되었다.

 

그래서 문제를 해결하기 위해 사각형의 사이즈를 2배로 해서 계산했다. 이렇게 수정할 경우

 

위와 같이 이동할 수 있는 경로가 확실하게 구분되기 때문에 BFS로 풀 수 있게 된다.

​

[아이디어 정리]

1. 사각형의 Size를 2배로 키운다
2. for문으로 사각형을 하나 선택하고, 테두리 경로를 그린다. 이후 다른 사각형과 겹치는 부분을 0으로 바꾼다.
3. 2번에서 구한 사각형의 경로를 map에 기록한다.
4. map을 전부 그렸으면, BFS로 횟수를 구한다.
5. BFS로 구한 횟수를 2로 나누어준다.(사각형의 크기를 2배했으므로 이동 횟수를 2로 나누면 된다.)

 

 

Code

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> map;
vector<vector<int>> copyMap;
int ldx,ldy,rux,ruy, oldx, oldy, orux, oruy;

int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int mSize=102;
void function()
{
    //4가지 경우 밖에 없다
    for (int i = oldx+1; i<orux; i++)
    {
        for (int j=oldy+1; j<oruy; j++)
        {
            copyMap[j][i]=0;
        }
    }
}

int BFS(int sty, int stx,int ty,int tx)
{
    queue<pair<int,int>> Queue;
    queue<int> qCnt;
    Queue.push(make_pair(sty,stx));
    qCnt.push(0);
    pair<int,int> nQ;
    int py,px, pCnt;
    while (true)
    {
        nQ=Queue.front();
        Queue.pop();
        pCnt=qCnt.front();
        qCnt.pop();
        for (int i=0; i<4; i++)
        {
            py=nQ.first+dy[i];
            px=nQ.second+dx[i];
            if (0<=py&&py<mSize&&0<=px&&px<mSize&&map[py][px]==1)
            {
                map[py][px]=0;
                Queue.push(make_pair(py,px));
                qCnt.push(pCnt+1);
                if (py==ty && px==tx)
                {
                    return pCnt+1;
                }
            }
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    map=vector<vector<int>>(mSize,vector<int>(mSize,0));
    for (int i=0; i<rectangle.size(); i++)
    {
        ldx=rectangle[i][0]*2;
        ldy=rectangle[i][1]*2;
        rux=rectangle[i][2]*2;
        ruy=rectangle[i][3]*2;
        copyMap=vector<vector<int>>(mSize,vector<int>(mSize,0));
        for (int j=ldx; j<=rux; j++)
        {
            copyMap[ldy][j]=1;
            copyMap[ruy][j]=1;
        }
        for (int j=ldy; j<=ruy; j++)
        {
            copyMap[j][ldx]=1;
            copyMap[j][rux]=1;
        }
        for (int j=0; j<rectangle.size(); j++)
        {
            if (j!=i)
            {
                oldx=rectangle[j][0]*2;
                oldy=rectangle[j][1]*2;
                orux=rectangle[j][2]*2;
                oruy=rectangle[j][3]*2;
                function();
            }
        }
        for (int y=0; y<mSize; y++)
        {
            for (int x=0; x<mSize; x++)
            {
                if (copyMap[y][x]==1)
                {
                    map[y][x]=1;
                }
            }
        }
    }
    answer = BFS(characterY*2, characterX*2, itemY*2,itemX*2);
        
    return answer/2;
}

 

---

 

 

처음에 map을 그릴 때 조건으로 이동 경로를 그리려고 해서 전역변수를 사용한게 살짝 남아있다

그래서 코드가 조금 더러워 보이네...

 

생각보다 어려우면서 생각보다 쉬운? 문제

 

프로그래머스