[프로그래머스 Level 3] 아이템 줍기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

 

특정 좌표에서 이동을 bfs를 이용했다. 동서남북으로 이동할 수 있도록 만들었고, 이 때 도형 내부와 외부에 들어갔을 때를 대비해 도형 내부와 도형 테두리에 대해 bool 타입 변수를 선언하여 이동한 좌표가 도형 내부이거나 테두리가 아닐 경우 queue에 안 넣는 방식으로 진행했다. 구현을 완료하고 테스트해보니 이상한 값이 나와 살펴보던 중, 아래 사진과 같이 길이가 테두리를 통해 이동하지 않고 한 칸 위로 건너 뛰었는데 테두리인 경우에도 bfs가 통과되는 것을 발견했다. 이를 위해 중간에 중간에 0.5 값을 줘야겠다 생각했는데 배열에 소수값을 줄 수 없어 좌표 평면을 2배씩 확장하여 이 문제를 해결했더니 문제가 풀렸다. 

 

#include <queue>

using namespace std;

bool edge[101][101];
bool interior[101][101];
bool checked[101][101];

int moveX[4] = {1,-1,0,0};
int moveY[4] = {0,0,1,-1};

queue<pair<int, pair<int, int>>> q;

int bfs(int x, int y, int a, int b) {
    q.push({0, {x,y}});
    checked[x][y]=true;
    while(!q.empty()){
        int val = q.front().first;
        int nodeX = q.front().second.first;
        int nodeY = q.front().second.second;
        q.pop();
        if(nodeX==a && nodeY==b){
            return val;
        }
        for(int i = 0; i<4; i++){
            int newX = nodeX+moveX[i];
            int newY = nodeY+moveY[i];
            if(checked[newX][newY]||(interior[newX][newY]||!edge[newX][newY])){
                continue;
            }
            checked[newX][newY]=true;
            q.push({val+1, {newX, newY}});
        }
    }
    return 0;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    
    for(int i = 0 ; i< rectangle.size(); i++){
        for(int m = rectangle[i][1]*2; m<=rectangle[i][3]*2; m++){
            for(int n = rectangle[i][0]*2; n<=rectangle[i][2]*2; n++){
                if(n==rectangle[i][0]*2 || n==rectangle[i][2]*2 ||
                   m==rectangle[i][1]*2 || m==rectangle[i][3]*2){
                    edge[n][m] = true;
                }else {
                    interior[n][m]=true;
                }
            }
        }
    }
    answer = bfs(characterX*2, characterY*2, itemX*2, itemY*2)/2;
    return answer;
}