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

문제

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

풀이

보드 위에서 한 칸씩 움직이며 최단 경로를 찾아야 하므로, BFS를 이용해 문제를 해결했다.

최단 거리가 예시보다 계속 짧게 나와서 각 이동 경로의 좌표를 출력해보았는데, 아래 이미지에서와 같이 (3, 5)에서 (3, 6)으로 이동하고 있었다. 테두리를 건너 뛰고 이동하는 것을 미처 생각하지 못했고, 전체 보드의 크기를 2배로 확장시켜 문제를 해결했다.

소스 코드

C++17

#include <bits/stdc++.h>

std::pair<int, int> operator+(const std::pair<int, int> &lhs, const std::pair<int, int> &rhs) {
    std::pair<int, int> ret(lhs);
    ret.first += rhs.first;
    ret.second += rhs.second;
    return ret;
}

constexpr std::pair<int, int> DIRECTIONS_4[4] = {
    { -1, 0 },
    {  0, 1 },
    {  1, 0 },
    { 0, -1 },
};

constexpr std::pair<int, int> DIRECTIONS_8[8] = {
    { -1,  0 },
    {  0,  1 },
    {  1,  0 },
    {  0, -1 },
    { -1, -1 },
    { -1,  1 },
    {  1,  1 },
    {  1, -1 }
};

std::vector<std::vector<int>> build_board(const std::vector<std::vector<int>> &rectangles) {
    int N = 0, M = 0;

    for (const auto &rectangle: rectangles) {
        N = std::max(N, rectangle[2]);
        M = std::max(M, rectangle[3]);
    }

    std::vector<std::vector<int>> ret(2 * (N + 1), std::vector<int>(2 * (M + 1), 0));

    for (const auto &rectangle: rectangles) {
        for (int i = 2 * rectangle[0]; i <= 2 * rectangle[2]; i++) {
            for (int j = 2 * rectangle[1]; j <= 2 * rectangle[3]; j++) {
                ret[i][j] = 1;
            }
        }
    }

    return ret;
}

int solution(std::vector<std::vector<int>> rectangles, int characterX, int characterY, int itemX, int itemY) {
    const auto &board = build_board(rectangles);
    std::queue<std::array<int, 3>> queue;
    std::vector<std::vector<int>> visited(board.size(), std::vector<int>(board[0].size(), 0));

    auto is_outline = [&] (const std::pair<int, int> &pos) {
        const auto [ r, c ] = pos;

        if (board[r][c] == 0) {
            return false;
        }

        for (const auto &direction: DIRECTIONS_8) {
            const auto [ nr, nc ] = pos + direction;
            if (board[nr][nc] == 0) {
                return true;
            }
        }

        return false;
    };

    visited[2 * characterX][2 * characterY] = true;
    queue.push({ 2 * characterX, 2 * characterY, 0 });
    while (!queue.empty()) {
        const auto [ r, c, distance ] = queue.front(); queue.pop();

        if (r == 2 * itemX && c == 2 * itemY) {
            return distance / 2;
        }

        for (const auto &direction: DIRECTIONS_4) {
            const auto [ nr, nc ] = std::pair<int, int>{ r, c } + direction;

            if (!visited[nr][nc] && is_outline({ nr, nc })) {
                visited[nr][nc] = true;
                queue.push({ nr, nc, distance + 1 });
            }
        }
    }

    return -1;
}

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

문제

풀이

소스 코드

Share this post