[C++] 아이템 줍기

요약

• BFS 적용

풀이 과정

BFS를 적용해서 상, 하, 좌, 우로 갈 때 해당 좌표가

1. 특정 rectangle의 내부에 있지 않고

   bool inRect(vector<vector<int>> rectangle, int x, int y) {  
   //하나라도 rect 안이면 true
    for(vector<int> r : rectangle)
    {
        if((r[0] < x && x < r[2]) &&(r[1] < y && y < r[3]))
            return true;
    }
    return false;
   }

2. 1-50사이 범위이며
3. rectangle의 선 위에 있는 좌표

   bool onRectLine(vector<vector<int>> rectangle, int x, int y) {
    for(vector<int> r : rectangle)
    {
        if((x==r[0] && (r[1] <= y && y <= r[3])) ||
           (y==r[1] && (r[0] <= x && x <= r[2])) ||
           (x==r[2] && (r[1] <= y && y <= r[3])) ||
           (y==r[3] && (r[0] <= x && x <= r[2])))
            return true;
    }
    return false;
   }

라면 큐에 추가했다.

문제는...

이런 경우도 3번에서 true가 나와버린다는 점이었다.
결국 이 부분을 해결하지 못했다.
이후 검색해보았는데 좌표를 모두 2배처리 하는 방식으로 해결하였다는 것을 확인하고 놀랐다.

또한, 내가 서술한 위 방식은 함수 호출을 할 때마다 반복문을 돌면서 매번 같은 직사각형의 내부/선위를 검사하고 있다. (DP적 관점에서 매우 비효율적)
이 대신에 더욱 간단한 방법을 확인할 수 있었다.

1. 좌표평면에 대응되는 2차원 배열 생성(0초기화)
2. 모든 직사각형의 line에 대해 1을 입력해줌
3. 모든 직사각형의 내부에 대해 0을 입력해줌

다시 정리해보겠다.

1. 모든 좌표 2배

    for(vector<int>& v : rectangle)
    {
        for(int& item : v)
            item *= 2;
    }
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;

2. 좌표 평면에 대응되는 2차원 배열 생성 및 0 초기화

int xy[102][102] = {0,};
범위를 101, 101으로 안한 이유가 있다.
이렇게 하면 x,y 조건 검사할 때 범위 검사를 안해도 된다.
무슨 말이냐면...
int xy[101][101] = {0,}
이렇게 하게 되면 배열의 마지막이 1인채로 끝나게 된다.
조건 검사를 해줘야 한다는 의미다.

대신 이 외곽선들이 반드시 0으로 둘러싸이도록 하면, 조건검사를 할 필요가 없어진다. 그냥 0이면 무조건 아닌거다.

3. 직사각형에 대해 1 입력

    for(auto r : rectangle)
    {
        for(int x = r[0]; x <= r[2]; x++)
        {
            for(int y = r[1]; y <= r[3]; y++)
            {
                xy[x][y] = 1;
            }
        }
    }

4. 직사각형의 내부에 대해 0 입력

    for(auto r : rectangle)
    {
        for(int x = r[0]+1; x < r[2]; x++)
        {
            for(int y = r[1]+1; y < r[3]; y++)
                xy[x][y] = 0;
        }
    }

이렇게 나온다.
출력시켜보면

[TC 1]

[TC 2]

이런 느낌이다.
이 배열을 visited 겸사겸사 쓸 수 있다.

5. BFS

while 전 선언

    queue<pair<coord,int>> q;   //coord, depth
    q.push(make_pair(coord(characterX,characterY),0));
    int temp[2] = {-1,1};

BFS는 역시 Queue. 첫 start player의 좌표를 넣어준다.
temp는 그냥 상/하/좌/우 다 입력할 필요가 없게 하려고 만든 배열.

while 내부

x,y는 temp[i]를 각각 더해주고 이 값이 xy 배열에서 1인지만 검사한다. target 값이 맞다면 depth에서 2로 나눠야 하는 점을 잊지 말 것!
또한, queue에 push하고 나서 현재 좌표를 xy 배열에서 0으로 만들어줘야(=방문 처리 해줘야) 무한 루프에 빠지지 않는다.

    while(!q.empty())
    {   
        coord cur(q.front().first.x, q.front().first.y);
        int depth = q.front().second;
        q.pop();

        for(int i = 0; i < 2; i++)
        {
            //x 검사
            if(xy[cur.x+temp[i]][cur.y] == 1)
            {   //x+temp[i]가 외곽선 위라면
                if(cur.x+temp[i] == itemX && cur.y == itemY)
                {   
                    return (depth+1)/2;
                }
                else
                {
                    xy[cur.x][cur.y] = 0;
                    q.push(make_pair(coord(cur.x+temp[i],cur.y),depth+1));
                }
            }
            //y 검사
            if(xy[cur.x][cur.y+temp[i]] == 1)
            {   //y+temp[i]가 외곽선 위라면
                if(cur.x == itemX && cur.y+temp[i] == itemY)
                {   
                    return (depth+1)/2;
                }
                else
                {
                    xy[cur.x][cur.y] = 0;
                    q.push(make_pair(coord(cur.x,cur.y+temp[i]),depth+1));
                }
            }
        }
    }

코드

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

#include <iostream>

using namespace std;

struct coord{
    int x;
    int y;
    coord(int a, int b) : x(a), y(b) {};
};


int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    for(vector<int>& v : rectangle)
    {
        for(int& item : v)
            item *= 2;
    }
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;

    int xy[102][102] = {0,};

    for(auto r : rectangle)
    {
        for(int x = r[0]; x <= r[2]; x++)
        {
            for(int y = r[1]; y <= r[3]; y++)
            {
                xy[x][y] = 1;
            }
        }
    }

    for(auto r : rectangle)
    {
        for(int x = r[0]+1; x < r[2]; x++)
        {
            for(int y = r[1]+1; y < r[3]; y++)
                xy[x][y] = 0;
        }
    }

    // for(int i = 0; i < 100; i++)
    // {
    //     for(int j = 0; j < 100; j++)
    //         cout << xy[i][j];
    //     cout << endl;
    // }

    queue<pair<coord,int>> q;   //coord, depth
    q.push(make_pair(coord(characterX,characterY),0));
    int temp[2] = {-1,1};

    while(!q.empty())
    {   
        coord cur(q.front().first.x, q.front().first.y);
        int depth = q.front().second;
        q.pop();

        for(int i = 0; i < 2; i++)
        {
            //x 검사
            if(xy[cur.x+temp[i]][cur.y] == 1)
            {   //x+temp[i]
                if(cur.x+temp[i] == itemX && cur.y == itemY)
                {   
                    return (depth+1)/2;
                }
                else
                {
                    xy[cur.x][cur.y] = 0;
                    q.push(make_pair(coord(cur.x+temp[i],cur.y),depth+1));
                }
            }
            //y 검사
            if(xy[cur.x][cur.y+temp[i]] == 1)
            {   //y+temp[i]
                if(cur.x == itemX && cur.y+temp[i] == itemY)
                {   
                    return (depth+1)/2;
                }
                else
                {
                    xy[cur.x][cur.y] = 0;
                    q.push(make_pair(coord(cur.x,cur.y+temp[i]),depth+1));
                }
            }
        }
    }
}

기억할 점

• 어려운 문제를 단순히 모든 좌표 X2만 해서 푼다는 발상이 정말 대단한 것 같다.
  역시 뇌가 말랑해야...😂
• 외곽선 처리 역시 저렇게 간단하게 할 수 있다는 점에 또 놀람.

배운 게 많은 문제였다.

다른사람의 풀이

애초에 내가 못풀어서 다른 사람의 풀이를 참조하였으므로...
다른 사람들 대부분의 key point는 좌표를 2배로 만든다는 점이었다.