프로그래머스 - 아이템 줍기

프로그래머스 - 아이템 줍기

위와 같이 사각형들이 여러개 주어지고, 그 들의 edge만 타고 갔을 때, 빨강점과 파랑점을 잇는 최단거리를 찾는 문제이다.
처음 시작할 때 갈 수 있는 방향의 경우의 수는 2가지 이기 때문에 미리 구한 뒤 2개에 대해서 시뮬레이션만 해주면 되는 문제이다.

x, y랑 row, col이 헷갈려서 보기 편하게 이를 치환하는 연산을 추가적으로 해줬다.

문제를 푼 방법은 다음과 같다.

1. map에서 사각형들이 차지하는 공간을 +1씩. (겹쳐진 공간은 자동적으로 +2, +3 ...)

• 이 때 주의해야 할 점은 x, y에 대해서 2배를 해줘야 한다는 점이다.
• (3, 4) ~ (4, 7)로 주어지면 이를 2배로 늘려서 (6, 8) ~ (8, 14) 구간에 +1씩 해주어야 한다.
• 2배를 하지 않으면 위 예제의 경우 (3, 5) (3, 6) (4, 6), (4,5) 부분이 모두 이어진 것 처럼 보인다.
• 따라서 이를 방지하기 위해서 격자 사이의 빈 공간을 채워넣어주어야 한다.

2. 그 후 사각형 내부의 공간을 0으로 비워준다.

• 해당 연산을 수행하지 않으면 [[2, 1, 3, 9], [1, 6, 12, 8], [7, 2, 9, 10], [4, 3, 11, 5]] 2 8 6 5 예제의 결과가 21이 아니라 13이 나온다.
• 그 이유는 사각형의 너비가 가장 얇은 경우 사각형 내부를 비워주지 않으면 사각형 내부도 마치 edge 처럼 생각하고 사각형을 뚫고 지나가기 때문이다.
• 물론 이 예외는 내 구현에서 그런 거고, 가려는 곳이 사각형 edge를 타고 가는 것인지, 뚫고 지나가는 것인지 좀 더 꼼꼼하게 체크해준다면 내부를 굳이 비워주지 않아도 될 것 같다. 내부를 비워주면 위 그림에 대해서는 다음 그림과 같이 사각형이 만들어진다.
  
• 2의 경우 교차점이고 1의 경우 edge가 된다.

3. 시작 지점을 기준으로 갈 수 있는 방향을 미리 2개 구한 뒤, 조건을 체크해주면서 x, y를 update해주면서 도착 지점에 다다를 때까지 step을 count한다.

4. 구해진 step 2개 중 작은 것을 answer로 리턴한다.

1, 2번만 구현하면 3, 4번은 금방한다.
3번의 경우 새로 도달한 곳이 1일 때는 direction을 유지하고, 2일 때는 direction을 수정하는 방식으로 구현하면 좀 더 빠르게 할 수 있을 것 같다.

코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX_XY 110
int map[MAX_XY][MAX_XY];
int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, 1, 0, -1 };
int possible_way[2] = { -1, -1 };

void print_map() {
    for(int i=80;i<MAX_XY;i++) {
        for(int j=0;j<40;j++) 
            printf("%d ", map[i][j]);
        printf("\n");
    }
}
const inline bool is_edge(int row, int col)
{
    if(map[row - 1][col - 1] == 0 || map[row - 1][col] == 0 || map[row - 1][col + 1] == 0 ||
       map[row][col - 1] == 0 || map[row][col + 1] == 0 ||
       map[row + 1][col - 1] == 0 || map[row + 1][col] == 0 || map[row + 1][col + 1] == 0) 
        return true;
    return false;
}
void tuning_map()
{
    int tmp[MAX_XY][MAX_XY];
    for(int i=0;i<MAX_XY;i++)
        memset(tmp[i], 0, sizeof(tmp[i]));
    
    for(int row=0;row<MAX_XY;row++) {
        for(int col=0;col<MAX_XY;col++) {
            if(map[row][col] == 0)
                continue;
            if(row - 1 < 0 || col - 1 < 0 || row + 1 >= MAX_XY || col + 1 >= MAX_XY)
                continue;
            if(is_edge(row, col))
                continue;
            tmp[row][col] = 1;
        }
    }
    for(int i=0;i<MAX_XY;i++) 
        for(int j=0;j<MAX_XY;j++)
            map[i][j] = tmp[i][j] == 1 ? 0 : map[i][j];
}

const inline bool is_safe(int row, int col)
{
    if(row < 0 || col < 0 || row >= MAX_XY || col >= MAX_XY)
        return false;
    return true;
}
const inline bool right_way(int newY, int newX, int tmpY, int tmpX)
{
    if((map[newY][newX] == 1 || map[newY][newX] == 2) && map[tmpY][tmpX] == 1)
        return true;
    return false;
}

const inline void find_possible_way(int characterY, int characterX) 
{
    int curX = characterX * 2;
    int curY = MAX_XY - characterY * 2 - 1;
    int way = 0;
    for(int i=0;i<4;i++) {
        int newX = curX + dirX[i] * 2;
        int newY = curY + dirY[i] * 2;
        if(!is_safe(newX, newY))
            continue;
        int tmpX = curX + dirX[i];
        int tmpY = curY + dirY[i];
        if(right_way(newY, newX, tmpY, tmpX)) 
            possible_way[way++] = i;
    }
}
const inline bool is_finish(int curY, int curX, int itemY, int itemX)
{
    if(curY == itemY && curX == itemX)
        return true;
    return false;
}
int solve(int idx, int characterY, int characterX, int itemY, int itemX)
{
    int curX = characterX * 2;
    int curY = MAX_XY - characterY * 2 - 1;
    int step = 0;
    int newX, newY;
    int beforedir = 5;
    int start_dir = possible_way[idx];
    itemY = MAX_XY - itemY * 2 - 1;
    itemX = itemX * 2;
    while(1) {
        if(is_finish(curY, curX, itemY, itemX))
            break;
        for(int i=0;i<4;i++) {
            if(step == 0)
                if(i != possible_way[idx])
                    continue;
            newX = curX + dirX[i] * 2;
            newY = curY + dirY[i] * 2;
            if((i + 2) % 4 == beforedir)
                continue;
            if(!is_safe(newX, newY))
                continue;
            int tmpX = curX + dirX[i];
            int tmpY = curY + dirY[i];
            if(right_way(newY, newX, tmpY, tmpX)) {
                map[curY][curX] = 7;
                curX = newX;
                curY = newY;
                step++;
                beforedir = i;
                break;
            }
        }
    }
    return step;
}
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++) {
        int col_start = rectangle[i][0] * 2;
        int col_end = rectangle[i][2] * 2;
        for(int col = col_start; col <= col_end; col++) {
            int row_start = (MAX_XY - rectangle[i][3]*2 - 1);
            int row_end = (MAX_XY - rectangle[i][1]*2 - 1);
            for(int row = row_start; row <= row_end; row++) 
                map[row][col]++;
        }
    }
    tuning_map();
    find_possible_way(characterY, characterX);
    int step[2] = { 0, 0 };
    for(int i=0;i<2;i++) 
        step[i] = solve(i, characterY, characterX, itemY, itemX);
        
    answer = min(step[0], step[1]);
    return answer;
}