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

문제 링크

1. 문제 접근 과정🧐

1. 테두리만 이동할 수 있으므로 직사각형의 외부와 내부를 1, 0으로 처리하여 이동 가능 여부를 판단
2. 좌표를 바로 사용하면 예시로 (3, 5)과 (3, 6) 서로 떨어져 있는데 BFS나 DFS를 하면 붙어 있다고 판단하게 되므로 각 좌표를 2배로 늘려 처리하는 것이 핵심
3. 모든 좌표를 2배로 늘렸으므로 BFS 후 답을 2로 나눈 것이 정답

2. 시행착오🤯

• 처음에 접근 방식을 구상하지 못해 gpt와 제미나이를 활용하여 힌트를 받았다.
  • 문제의 핵심은 좌표를 2배로 늘려 처리하는 것
  • 내부, 외부 1과 0으로 처리하는 로직은 따로 하는 것이 안전
• 내부와 외부를 따로 하는 것이 안전한 이유는 직사각형이 서로 겹쳐있어 한 반복문 안에 모두 처리하면 겹쳐진 부분이 테두리로 표시될 수 있기 때문이다.

3. 개선한 코드😄

• 접근 방식을 토대로 BFS로 구현하여 해결
  
• 정답 코드

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

using namespace std;

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int answer = 0;
    vector<vector<int>> board(101, vector<int>(101, 0));
    for(int i = 0; i < rectangle.size(); i++){
        int x1 = rectangle[i][0], y1 = rectangle[i][1], x2 = rectangle[i][2], y2 = rectangle[i][3];
        for(int i = x1 * 2; i <= x2 * 2; i++){
            for(int j = y1 * 2; j <= y2 * 2; j++){
                board[i][j] = 1;
            }
        }
    }
    for(int i = 0; i < rectangle.size(); i++){
        int x1 = rectangle[i][0], y1 = rectangle[i][1], x2 = rectangle[i][2], y2 = rectangle[i][3];
        for(int i = x1 * 2 + 1; i <= x2 * 2 - 1; i++){
            for(int j = y1 * 2 + 1; j <= y2 * 2 - 1; j++){
                board[i][j] = 0;
            }
        }
    }
    queue<tuple<int, int, int>> q;
    q.push({characterX * 2, characterY * 2, 0});
    vector<vector<int>> visited(101, vector<int>(101, 0));
    visited[characterX * 2][characterY * 2] = 1;
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    while(!q.empty()){
        int x = get<0>(q.front()), y = get<1>(q.front()), cur = get<2>(q.front());
        q.pop();
        if(x == itemX * 2 && y == itemY * 2){
            answer = cur;
            break;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= 101 || ny < 0 || ny >= 101) continue; 
            if(!visited[nx][ny] && board[nx][ny]){
                visited[nx][ny] = 1;
                q.push({nx, ny, cur + 1});
            }
        }
    }
    return answer / 2;
}

4. 회고💭

• 문제를 풀 때 어느 정도 시간적 여유를 가져 생각해보고 구글링이나 AI를 활용하여 힌트를 얻어 안되는 것을 계속 생각하는 것보다 시간적, 문제 접근 측면에서 도움이 되는 것 같다.
  • 정말 모를 것 같을 때는 힌트를 얻어 접근해보자!