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

풀이

bfs문제였다.

관건읜 직사격형의 외각만 딴 경로를 그리는 것이였다. 

임의의 좌표에 대해서 어떠한 사각형 내부에 (선 제외) 있다면 외각선이 아니므로 체크해주지 않는다.

위의 조건을 통과하는 점들은 외곽선에 있는지 체크하고 좌표를 true로 바꾸어 주었다.

문제는 배열의 좌표만 가지고 판단한다면 3,5와 3,6 둘 다  true여서 이동할 수 있는 것처럼 보인다.

(바로 옆에 있기 때문에)
해법은 검색해서 찾았다.

모든 좌표를 2배로 해서 계산하면된다. 그리고 답을 2로 나누어서 제출하면된다.

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

vector<vector<bool>>visit(101,vector<bool>(101,false));
vector<vector<bool>>map(101,vector<bool>(101,false));
vector<vector<int>>dist(101,vector<int>(101,false));


int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    for(int i=0;i<101;i++){
        for(int j=0;j<101;j++){
            for(int k=0;k<rectangle.size();k++){
                //내부에 있으면 false continue;
                if(i>rectangle[k][1]*2 && i<rectangle[k][3]*2 && j>rectangle[k][0]*2 &&j<rectangle[k][2]*2)
                {
                    map[i][j]=false;
                    break;
                }
                // 아웃라인 체크
                if(i==rectangle[k][1]*2 || i==rectangle[k][3]*2 )
                    if(j>=rectangle[k][0]*2 && j<=rectangle[k][2]*2)
                    {
                        map[i][j]=true;
                        continue;
                    }
                if(j==rectangle[k][0]*2 || j==rectangle[k][2]*2 )
                    if(i>=rectangle[k][1]*2 &&i<=rectangle[k][3]*2)
                    {
                        map[i][j]=true;
                        continue;
                    }
            }
        }
    }

    queue<pair<int,int>>q;
    q.push({characterY*2,  characterX*2});
    int dy[] = {0,1,0,-1};
    int dx[] = {1,0,-1,0};
    while(!q.empty()){
        int y = q.front().first;
        int x= q.front().second;
        q.pop();
        visit[y][x]=true;
        if(y== itemY*2 && x==itemX*2){
            answer= dist[y][x]/2;
            break;
        }
        
        for(int i=0;i<4;i++){
            int next_y = y + dy[i];
            int next_x = x + dx[i];
            if(next_y<0 || next_y>100 || next_x<0  ||next_x>100)
                continue;
            if(visit[next_y][next_x])
                continue;
            if(map[next_y][next_x]){
                visit[next_y][next_x]=true;
                q.push({next_y,next_x});
                dist[next_y][next_x]=dist[y][x]+1;
            }
        }
        
    }
    
    return answer;
}