[Lv.3] 아이템 줍기

출처. 프로그래머스

프로그래머스

 

문제를 풀다가 여러 난관에 부딪혔던 문제....

 

난관 1. 사각형이 겹쳐 있을때, 태두리 둘레를 어떻게 알지?

 - 해결방법 : 사각형 좌표가 주어지면 넓이를 모두 1로 칠한다. 그리고 테두리를 제외한 나머지를 0으로 바꾼다.

 

주어진 모든 사각형을 1로 칠한 모습

 

맨 아래사각형 테두리만 제외하고 0으로 칠한 모습

 

그 다음 사각형 테두리 제외하고 0으로 칠한 모습

 

다른 사각형도 반복하면, 테두리만 남는다!

 

이 맵을 가지고 캐릭터 위치에서 출발하여 아이템까지 가는 최단 경로를 DFS로 구하면 되는지 알았지만.....

그러면 대차게 틀림.

 

난관 2. 사각형 테두리끼리 맞다은 경우에 이동경로 설정이 안됨.

 - 아래와 같이 테두리가 있는 경우에 위오른쪽에서 세번째 1(색칠된 1)에서 인접한 1로 갈때, 왼쪽으로만 가야하는데 아래쪽으로도 갈수있도록 되어버림.

난관 2를 어떻게 하지 고민이 많았는데, 방법은 간단하게 주어진 사각형의 크기를 모두 2배씩 하면 됨.

그렇게 되면 아래와 같이 경로가 그려지게 되서 인접한 1로 찾아갈수가 있음!

 

최단경로를 찾으면 처음에 길이를 2배 했으니, 경로를 나누기 2하면 정답!

 

구현 내용은 아래 코드 참고

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

using namespace std;

// 입력한 점을 2배하기 위해서, 그려질 맵도 2배
int map[102][102]{};

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

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    // 입력된 점을 2배하기
    for (size_t 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;
        
        // 사각형 전체를 1로 칠하기
        for (size_t y = y1 ; y <= y2 ; y++) {
            for (size_t x = x1 ; x <= x2 ; x++) {
                map[y][x] = 1;
            }
        }
    }
    
    // 입력된 점을 2배하기
    for (size_t 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;
        
        // 사각형 내부를 0로 칠하기
        for (size_t y = y1 + 1 ; y < y2 ; y++) {
            for (size_t x = x1 + 1 ; x < x2 ; x++) {
                map[y][x] = 0;
            }
        }
    }
    
    // DFS로 아이템을 만나는 최단경로 찾기
    queue<pair<int,int>> nextPos;
    nextPos.push({characterY * 2, characterX * 2});
    
    int answer = 0;
    bool isBreak = false;
    while (!nextPos.empty() && !isBreak) {
        size_t loopCnt = nextPos.size();
        
        for (size_t cnt = 0 ; cnt < loopCnt ; cnt++) {
            pair<int,int> cur = nextPos.front(); nextPos.pop();
            
            for (size_t idx = 0 ; idx < 4 ; idx++) {
                int ny = cur.first + dy[idx];
                int nx = cur.second + dx[idx];
                
                if (0<nx && nx<=101 && 0<ny && ny<=101 && (map[ny][nx] == 1)) {
                    map[ny][nx] = 0; // 한번 간곳은 안가기 위해서 0으로 
                    
                    if ((nx == itemX * 2) && (ny == itemY*2)) { // 찾았다!
                        isBreak = true;
                    }
                    
                    nextPos.push({ny,nx});
                }
            }
        }
        
        answer++;
    }
    
    return answer/2;
}