[프로그래머스] 아이템 줍기 (C++)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

풀이

처음 문제를 보았을 때 이걸 어떻게 풀지... 라는 막연한 생각이 드는 문제이다.

특히 직사각형의 외곽만을 따라 경로를 설정하는 것이 난감할 수 있는데 이는 생각보다 쉽게 구현할 수 있다.

 

먼저 [1, 1, 7, 4]인 경우이다. 사각형의 내부는 전부 -1로 채워주고 외곽은 1로 채운다.

(-1은 연빨간색, 1은 하늘색)

 

이어서 [3, 2, 5, 5]인 경우이다. 마찬가지로 사각형의 내부는 전부 -1로 채워주고 외곽은 1로 채운다.

단, 외곽을 1로 채울 때 채우는 자리가 이미 -1이라면 채우지 않는다.

(이미 연빨간색으로 채워져있으면 파란색으로 채우지 않고 그대로 둔다.)

내부를 -1로 채울 때는 그 자리가 무엇이든 상관없이 -1로 채운다(연빨간색).

 

다음은 [4, 3, 6, 9]인 경우이다. 

 

마지막으로 [2, 6, 8, 8]인 경우이다.

그림으로만 보면 헷갈릴 수 있기 때문에 외곽을 따라 선을 그어서 경로를 표기하였다.

 

위와 같이 50 × 50 크기의 배열에 정보들을 저장하고

BFS 또는 DFS를 통해 경로를 찾게 될텐데 여기서 문제가 발생한다.

 

예를 들어 (3, 5)에서 경로를 찾는 경우 이동할 수 있는 경로는 (3, 4), (4, 5), (3, 6)으로 세 개이다.

하지만 (3, 6)은 실제 경로 상으로 (3, 5)에서 이동할 수 없는 칸이다.

이는 50 × 50 배열을 100 × 100으로 두 배 키우고 사각형의 크기도 두 배로 키우면 해결할 수 있다.

 

크기를 2배로 키우니 외곽 경로가 명확해졌고 경로를 찾을 때도 이상한 경로로 방문하는 일이 사라지게 되었다.

코드

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

using namespace std;

int graph[101][101];
bool visited[101][101];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

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 dot1X = rectangle[i][0];
        int dot1Y = rectangle[i][1];
        int dot2X = rectangle[i][2];
        int dot2Y = rectangle[i][3];
        
        // 직사각형 내부를 -1로 채움(이동 불가)
        for (int x = dot1X*2+1; x < dot2X*2; x++){
            for (int y = dot1Y*2+1; y < dot2Y*2; y++){
                graph[y][x] = -1;
            }
        }
        // 직사각형 외곽은 1로 채움(이동 가능)
        for (int x = dot1X*2; x <= dot2X*2; x++){
            if (graph[dot1Y*2][x] != -1){
                graph[dot1Y*2][x] = 1;    
            }
            if (graph[dot2Y*2][x] != -1){
                graph[dot2Y*2][x] = 1;
            }
        }
        for (int y = dot1Y*2; y <= dot2Y*2; y++){
            if (graph[y][dot1X*2] != -1){
                graph[y][dot1X*2] = 1;
            }
            if (graph[y][dot2X*2] != -1){
                graph[y][dot2X*2] = 1;
            }
        }
    }
        
    // bfs로 탐색
    queue<pair<int, int>> que;
    que.push({characterY*2, characterX*2});
    visited[characterY*2][characterX*2] = true;

    while (!que.empty()){
        int size = que.size();
        for (int s = 0; s < size; s++){
            int curY = que.front().first;
            int curX = que.front().second;

            que.pop();

            if (curY == itemY*2 && curX == itemX*2){
                return answer/2;
            }

            for (int i = 0; i < 4; i++){
                int nextY = curY + dir[i][0];
                int nextX = curX + dir[i][1];

                if (nextY < 2 || nextY > 100 || nextX < 2 || nextX > 100 
                    || visited[nextY][nextX] == true){
                    continue;
                }
                if (graph[nextY][nextX] == 1){
                    que.push({nextY, nextX});
                    visited[nextY][nextX] = true;
                }
            }
        }
        answer++;   
    }
    
    
    return answer;
}