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

풀이 소요시간 : 풀이 참고

한 15분정도 문제를 들여다보다가 풀이방법을 찾지 못해 정석 풀이를 참고하였다. 어떻게 겹친 사각형의 테두리 경로를 표기할 수 있는걸까 싶었는데 기가막힌 방법이 존재하고있었다. 무조건 암기해두자.

겹친 도형의 총 테두리를 표시하는 방법

1. 모든 도형의 테두리를 Map = 1 로 표기한다.
2. 모든 도형의 내부를 Map = 0 로 표기한다.

바로 이 방법이였다. 너무 쉬운 방법인데 도저히 떠올릴 수가 없었다.

예외 처리

하지만 이후 단순히 BFS를 구현하면 예외가 발생하게된다.

0 1 1
1 1 1

위의 경우처럼 도형의 너비가 1인 경우 테두리를 따라 탐색하지 않고 내부를 가로지를 수 있다는 것이다. 따라서 모든 좌표값 *2 를 해두고 탐색해야한다. 그리고 마지막 결과값을 /2로 반환받으면 된다.

전체 코드

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

int Map[101][101];
int Visit[101][101];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int Bfs(int sx, int sy, int gx, int gy) {
    
    queue<pair<pair<int, int>, int>> Q;
    Q.push({{sx, sy}, 0});
    Visit[sx][sy] = 1;
    
    while(!Q.empty())
    {
        int px = Q.front().first.first;
        int py = Q.front().first.second;
        int time = Q.front().second;
        Q.pop();
        
        if(px == gx && py == gy)
        {
            return time / 2;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int nx = px + dx[i];
            int ny = py + dy[i];
            
            if(Map[nx][ny] == 0) continue;
            if(Visit[nx][ny] == 1) continue;
            Visit[nx][ny] = 1;
            Q.push({{nx, ny}, time + 1});
        }
    }
    
    return 0;
}


int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    
    for(int i = 0; i < rectangle.size(); i++)
    {
        int x1 = rectangle[i][0] * 2;
        int y1 = rectangle[i][1] * 2;
        int x2 = rectangle[i][2] * 2;
        int y2 = rectangle[i][3] * 2;
        
        for(int i = x1; i <= x2; i++)
            for(int j = y1; j <= y2; j++)
                if(i == x1 || i == x2 || j == y1 || j == y2) Map[i][j] = 1; 
        //가장자리 이동 가능
    }
    
    for(int i = 0; i < rectangle.size(); i++)
    {
        int x1 = rectangle[i][0] * 2;
        int y1 = rectangle[i][1] * 2;
        int x2 = rectangle[i][2] * 2;
        int y2 = rectangle[i][3] * 2;
        
        for(int i = x1; i <= x2; i++)
            for(int j = y1; j <= y2; j++)
                if(!(i == x1 || i == x2 || j == y1 || j == y2)) Map[i][j] = 0; 
        //내부 이동 불가능
    }
    
    
    int sx = characterX * 2;
    int sy = characterY * 2;
    int gx = itemX * 2;
    int gy = itemY * 2;
    return Bfs(sx, sy, gx, gy);
    
}