프로그래머스 - 아이템 줍기 (C++)

프로그래머스 상에서 문제 분류는 DFS/BFS로 분류되어 있지만 탐색 로직을 만드는게 훨씬 오래걸리는 문제였다..

프로그래머스

---

문제는 결국 이 예시처럼 겹쳐져있는 사각형의 외곽부분을 경로삼아 목적지에 도달하는 최단 경로를 계산하면 된다. 최단 경로를 요구하니 BFS를 썼다. 이제 문제는 저 외곽선들을 어떻게 탐지해서 다음 목적지를 큐에 넣어주느냐이다.

 

일단 찾게 될 다음 경로들이 사각형의 내부에 들어가는지를 판별해야한다. 문제 설명상 플레이어는 내부로 들어갈 순 없기 때문에 이런 경우에는 false를 리턴해야 한다.

bool inRectangle (vector<vector<int>>& rectangle, float x, float y) {
    for(int i = 0; i < rectangle.size(); i++) {
        auto& point = rectangle[i];
        if(point[0] < x && x < point[2] && point[1] < y && y < point[3]) return true;
    }
    return false;
}

함수의 작동 구조는 위의 설명대로다. 여기서 사각형 내부로 들어가는 포인트(x,y)들은 걸러지게 된다.

 

그럼 이제 현재의 포인트를 받고, 그 주변의 포인트들을 탐색해서 리턴해주는 findline함수이다.

vector<pair<int,int>> findLine (vector<vector<int>>& rectangle, int x, int y) {
    vector<pair<int,int>> result;
    for(int i = 0 ; i < rectangle.size(); i++) {
        auto& point = rectangle[i];
        if(x == point[0] && point[1] <= y && y <= point[3]) {
            if(y+1 <= point[3]&& !inRectangle(rectangle, x, y+0.5)) result.push_back({x,y+1});
            if(y-1 >= point[1]&& !inRectangle(rectangle, x, y-0.5)) result.push_back({x,y-1});
        }
        if(x == point[2] && point[1] <= y && y <= point[3]) {
            if(y+1 <= point[3]&& !inRectangle(rectangle, x, y+0.5)) result.push_back({x,y+1});
            if(y-1 >= point[1]&& !inRectangle(rectangle, x, y-0.5)) result.push_back({x,y-1});
        }
        if(point[0] <= x && x <= point[2] && y == point[1]) {
            if(x+1 <= point[2]&& !inRectangle(rectangle, x+0.5, y)) result.push_back({x+1,y});
            if(x-1 >= point[0]&& !inRectangle(rectangle, x-0.5, y)) result.push_back({x-1,y});
        }
        if(point[0] <= x && x <= point[2] && y == point[3]) {
            if(x+1 <= point[2] && !inRectangle(rectangle, x+0.5, y)) result.push_back({x+1,y});
            if(x-1 >= point[0] && !inRectangle(rectangle, x-0.5, y)) result.push_back({x-1,y});
        }
    }
    return result;
}

일단 !inRectangle()부분을 생략하고 설명하자면,

for문을 도는 이유는 모든 사각형에 대해 탐색이 필요하기 때문이며(현재 포인트가 어떤 사각형 위에있는지 찾아야 하기 때문),

내부의 if(x == point[N] && point[M] <= y && y <= point[L]) {...} 형식의 첫번째 조건문은 사각형의 각 선분에 대응하는 조건문이다. 여기서 현재의 포인트가 특정 선분 안에 있다면 조건문 내부에 진입한다.

조건문 내부의 2개의 if문은 위/아래 또는 좌/우 방향으로의 다음 경로가 사각형의 범위를 벗어나지 않는지 확인하는 조건문이며, 이를 만족한다면 result에 추가한다. result에는 다음에 이동할 지점들이 쌓이게 된다.

 

inRectangle을 여기서 확인하는 이유는, 탐색 지점이 다른 사각형으로 덮여있으면 해당 지점은 경로에 추가하면 안되기 때문이다.

그리고 +1, -1을 넣지 않고 +0.5, -0.5를 넣어주는 이유는 아래와 같은 경우 때문이다.

엑셀로 그렸다

여기서 (2,5)에서 출발해서 (3,5)지점에 도착한뒤, 다음 경로를 계산하게 될때, 언뜻 보기엔 (3,6)만 다음 경로로 계산할것 같지만 +1,-1을 넣어주게 되면 (4,5)도 다음 경로로 계산한다. inRectangle함수의 계산 구조상 해당 지점은 사각형의 내부가 아니기 때문이다. 실제로 내부도 아니다.!

그래서 (3,5)의 다음 지점을 계산할때 (3.5,5)를 넣어준다. 이렇게 하면 해당 경로가 다른 사각형의 범위 안에 있는지 확인이 가능하다.

결론은, 소수점을 넣어주는 이유는 폭 또는 너비가 1인 사각형이 정확하게 경로 지점만 가로막고 있는 경우를 파훼하기 위함이다.

 

이제 BFS함수를 만든다.

bool visit[51][51] = {};
const int INF = numeric_limits<int>::max();

struct State {
    int x, y;
    int length;
};

int bfs(vector<vector<int>>& rectangle, int cX, int cY, int iX, int iY) {
    queue<State> q;
    int mini = INF;
    
    q.push({cX,cY,0});
    visit[cX][cY] = true;
    
    while(!q.empty()) {
        State current = q.front();
        q.pop();
        if(current.x == iX && current.y == iY) {
            mini = min(current.length, mini);
        }
        
        vector<pair<int,int>> adjPoint = findLine(rectangle, current.x, current.y);
        for(auto& [x,y] : adjPoint) {
            if(visit[x][y]) continue;
            q.push({x,y,current.length + 1});
            visit[x][y] = true;
        }
    }
    return mini;
}

별거 없다. 큐에 저장하는 정보는 State 구조체에 담는다. 필요한 정보는 현재의 좌표, 현재까지의 길이이다.

while문은 큐.pop한(탐색할) 현재 좌표가 목적지와 동일한지 확인하고, 동일하다면 mini 변수를 최소값으로 업데이트한다.

 

탐색할 인접좌표들은 findLine함수를 통해서 구하고, for문으로 돌아준다.

마지막으로 mini를 리턴해준다.

 

solution에서는 bfs의 결과값을 그대로 리턴해주면 된다. 아래는 전체 코드이다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <limits>

using namespace std;



bool inRectangle (vector<vector<int>>& rectangle, float x, float y) {
    for(int i = 0; i < rectangle.size(); i++) {
        auto& point = rectangle[i];
        if(point[0] < x && x < point[2] && point[1] < y && y < point[3]) return true;
    }
    return false;
}

vector<pair<int,int>> findLine (vector<vector<int>>& rectangle, int x, int y) {
    vector<pair<int,int>> result;
    for(int i = 0 ; i < rectangle.size(); i++) {
        auto& point = rectangle[i];
        if(x == point[0] && point[1] <= y && y <= point[3]) {
            if(y+1 <= point[3]&& !inRectangle(rectangle, x, y+0.5)) result.push_back({x,y+1});
            if(y-1 >= point[1]&& !inRectangle(rectangle, x, y-0.5)) result.push_back({x,y-1});
        }
        if(x == point[2] && point[1] <= y && y <= point[3]) {
            if(y+1 <= point[3]&& !inRectangle(rectangle, x, y+0.5)) result.push_back({x,y+1});
            if(y-1 >= point[1]&& !inRectangle(rectangle, x, y-0.5)) result.push_back({x,y-1});
        }
        if(point[0] <= x && x <= point[2] && y == point[1]) {
            if(x+1 <= point[2]&& !inRectangle(rectangle, x+0.5, y)) result.push_back({x+1,y});
            if(x-1 >= point[0]&& !inRectangle(rectangle, x-0.5, y)) result.push_back({x-1,y});
        }
        if(point[0] <= x && x <= point[2] && y == point[3]) {
            if(x+1 <= point[2] && !inRectangle(rectangle, x+0.5, y)) result.push_back({x+1,y});
            if(x-1 >= point[0] && !inRectangle(rectangle, x-0.5, y)) result.push_back({x-1,y});
        }
    }
    return result;
}

bool visit[51][51] = {};
const int INF = numeric_limits<int>::max();

struct State {
    int x, y;
    int length;
};

int bfs(vector<vector<int>>& rectangle, int cX, int cY, int iX, int iY) {
    queue<State> q;
    int mini = INF;
    
    q.push({cX,cY,0});
    visit[cX][cY] = true;
    
    while(!q.empty()) {
        State current = q.front();
        q.pop();
        if(current.x == iX && current.y == iY) {
            mini = min(current.length, mini);
        }
        
        vector<pair<int,int>> adjPoint = findLine(rectangle, current.x, current.y);
        for(auto& [x,y] : adjPoint) {
            if(visit[x][y]) continue;
            q.push({x,y,current.length + 1});
            visit[x][y] = true;
        }
    }
    return mini;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    return bfs(rectangle, characterX, characterY, itemX, itemY);
}