[Programmers] 아이템 줍기 (C++)

문제

직사각형들을 겹친 후 둘레를 따라 이동한다.

캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리는?

생각할 것

1. 겹친 사각형들의 테두리를 구해야 할 것이다
   1. 안쪽을 모두 1로 채운 뒤에 안쪽을 다시 비워서 테두리를 찾는다
2. 테두리가 인접한 경우 배열만 보고 테두리를 판단할 수 없다

   1. 

   2. 모든 좌표값을 2배로 늘린다.
   3. 물론 배열의 크기도 2배로!
3. BFS로 최단 경로를 탐색한 뒤 경로를 다시 2로 나누어준다.

코드

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

using namespace std;

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;

    // 사각형 모두 채우기 
    vector<vector<int>> map(101, vector<int>(101, 0));
    for(int i=0; i<rectangle.size(); i++){
        for(int x = rectangle[i][1] * 2; x <= rectangle[i][3] * 2; x++){
            for(int y = rectangle[i][0] * 2; y <= rectangle[i][2] * 2; y++){
                map[x][y] = 1;
            }
        }
    }
    
    // 테두리만 남기고 안쪽은 0으로 초기화
    for(int i=0; i < rectangle.size(); i++){
        for(int x = rectangle[i][1] * 2 + 1; x < rectangle[i][3] * 2; x++){
            for(int y = rectangle[i][0] * 2 + 1; y < rectangle[i][2] * 2; y++){
                map[x][y] = 0;
            }
        }
    }
    
    // 최단 경로 탐색
    int dx[4] = {-1, 1, 0, 0}; // 상하좌우
    int dy[4] = {0, 0, -1, 1}; 
    vector<vector<int>> visited(101, vector<int>(101, 0));
    queue<pair<int,int>> q;
    
    q.push(make_pair(characterY * 2, characterX * 2)); // 내가 설정한 x,y와 문제의 X, Y가 바뀌어 있음!
    visited[characterY * 2][characterX * 2] = 1;
    
    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        if(cx == itemY * 2 && cy == itemX * 2) break;
        for(int k=0; k<4; k++){
            int nx = cx + dx[k];
            int ny = cy + dy[k];
            if(!(0 < nx && nx < 101 && 0 < ny && ny < 101)) continue;
            if(visited[nx][ny]) continue;
            if(map[nx][ny]) {
                visited[nx][ny] = visited[cx][cy] + 1; 
                q.push({nx, ny});
            } else {
                visited[nx][ny] = visited[cx][cy]; 
            }
        }
    }
    
    return visited[itemY * 2][itemX * 2] / 2; // 배열을 2배 늘렸으므로 다시 최단 경로를 2로 나누어 주기
}