[PS] 아이템 줍기

프로그래머스

문제

- 주어진 사각형의 모서리만 따라서 이동하여 아이템 줍기

 

풀이

 

1. 모든 좌표를 2배수 하기

 

그림과 같은 모서리가 주어졌을 때, 좌표 기준으로 방문 가능 여부를 채우게 된다면

모서리가 아닌 부분까지 방문 가능하다고 착각할 수 있으므로 모든 좌표를 2배수 해야 한다.

 

 

2. 이동 가능한 범위 구하기 (사각형)

이동 가능한 범위는 사각형들의 모서리이다.

간단히 생각해서 사각형 범위들을 전부 1로 채우고, 내부는 0으로 채우면 끝!!

 

내가 여기서 의문이었던 것은, 그럼 겹치는 부분은 어떻게 되는거지?.. 였는데

예를 들어 아래와 같은 경우다.

 

 [B 사각형 내부에 있는 A 사각형 모서리]

 

그래서 곰곰히 생각해봤는데, 첫 번째 반복문으로 모든 사각형을 한번에 채우고

그 다음 반복문을 한번 더 돌려서 모든 사각형의 내부를 0으로 만들어야 한다.

그렇게 하면 B 사각형 내부에 있는 A 사각형 모서리도 0으로 채워진다.

 

코드

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

constexpr int MAX = 102;
int map[MAX][MAX] = {0};
int dist[MAX][MAX];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int characterX, int characterY, int itemX, int itemY, int &answer){
    queue<pair<int, int>> q;
    q.push({characterX, characterY});
    
    dist[characterY][characterX] = 0;

    while (!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        
        if (cx == itemX && cy == itemY) {
            answer = (dist[cy][cx]) / 2;
            break; 
        }
        
        for (int move = 0; move < 4; move++){
            int nextX = cx + dx[move];
            int nextY = cy + dy[move];
            
            if (nextX < 0 || nextX >= MAX || nextY < 0 || nextY >= MAX) continue;
            
            if (map[nextY][nextX] == 1 && dist[nextY][nextX] == -1){ 
                dist[nextY][nextX] = dist[cy][cx] + 1; 
                q.push({nextX, nextY});
            }
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    characterX *= 2, characterY *= 2, itemX *= 2, itemY *= 2;
    memset(dist, -1, sizeof(dist));

    for (auto r : rectangle){
        for (int y = 2 * r[1]; y <= 2 * r[3]; y++){
            for (int x = 2 * r[0]; x <= 2 * r[2]; x++){
                map[y][x] = 1;
            }
        }
    }
    
    for (auto r : rectangle){
        for (int y = 2 * r[1] + 1; y < 2 * r[3]; y++){
            for (int x = 2 * r[0] + 1; x < 2 * r[2]; x++){
                map[y][x] = 0;
            }
        }
    }
    
    bfs(characterX, characterY, itemX, itemY, answer);
    
    return answer;
}

 

 

회고

이 문제는 프로그래머스 상으로 레벨 3에 해당하기 때문에... 처음부터 겁을 먹고 들어갔다.

문제가 최근에 본 SOFTIEER 코테와 유사해서, 범위로 푸려고 시도했던 것 같다.

 

가능한 범위를 계산해서, 그중 모서리만 따라가게 하면 되겠다고 생각을 했었는데

사각형에서 모서리와 내부를 분리하는 과정이 너무 비효율적이라 판단해서

고민 1시간 + 구현 1시간 하다가 결국 정답을 보게됐다...

 

모든 좌표점을 2배수로 저장한다는 것은 생각치도 못한 아이디어였는데

2시간동안 고민한 덕분에... 이번 2배수 풀이가 확실히 기억에 남게 됐다.

다음엔 절대 안 틀릴지도?? ㅎㅎ.....

 

좀 더 공부를 해서, 나중에는 Level3를 내 힘으로 풀어보고 싶다!!!