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

🌽 문제

🥔 풀이

좌표를 두 배로 사용해야 아래와 같은 문제를 방지할 수 있다고 한다.
1. 사각형들이 붙어있거나 겹치는 경우
2. 사각형 내부의 겉모서리만 밟고 지나가야 할 때
3. 대각선 통과가 가능하게 되어 BFS가 잘못된 길을 허용하는 경우

auto& r: rectangle 이런거 잘 써먹고 싶은데 맨날 까먹는다.
auto [x, y] = q.front() 이건 기억해냈다.

마지막에 visited 값 원상복구하는 것 잊지 않기..
이 문제 다시 푸는 것도 잊지 않기..

🥬 코드

#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int map[102][102] = {0};
    int visited[102][102] = {0};

    for (auto& r : rectangle) {
        int x1 = r[0] * 2, y1 = r[1] * 2;
        int x2 = r[2] * 2, y2 = r[3] * 2;

        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                map[i][j] = 1;
            }
        }
    }

    for (auto& r : rectangle) {
        int x1 = r[0] * 2 + 1, y1 = r[1] * 2 + 1;
        int x2 = r[2] * 2 - 1, y2 = r[3] * 2 - 1;

        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                map[i][j] = 0;
            }
        }
    }

    queue<pair<int, int>> q;
    q.push({characterX * 2, characterY * 2});
    visited[characterX * 2][characterY * 2] = 1;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();

        if (x == itemX * 2 && y == itemY * 2) {
            return (visited[x][y] - 1) / 2;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= 102 || ny >= 102) continue;
            if (!map[nx][ny] || visited[nx][ny]) continue;

            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx, ny});
        }
    }

    return 0;
}

🥜 채점