[프로그래머스] 60063 블록 이동하기 (C/C++)

문제

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

풀이

어렵지 않은 BFS 문제였다. 문제에서 회전을 요구하여 행렬 회전 변환 코드를 구현할까 고민했는데, 경우의 수가 모양(가로, 세로) * 회전 방향(시계, 반시계) * 축(좌표1, 좌표2) = 총 8가지로 많지 않아 각 경우를 직접 구현했다. 로직 자체는 어렵지 않았지만, 코드를 깔끔하게 구현하는 게 어려운 문제였다.

메모

lvalue 참조를 사용할 때, 참조하는 대상이 유효한지 항상 확인하자.

소스 코드

C++17

#include <bits/stdc++.h>

typedef enum e_direction {
    UP = 0,
    RIGHT,
    DOWN,
    LEFT,
}   t_direction;

const std::vector<t_direction> VERTICAL = { UP, DOWN };
const std::vector<t_direction> HORIZONTAL = { LEFT, RIGHT };

typedef std::pair<int, int> Coordinate;
typedef std::pair<Coordinate, Coordinate> Location;

constexpr Coordinate OFFSETS[4] = {
    { -1, 0 },
    {  0, 1 },
    {  1, 0 },
    { 0, -1 },
};

Coordinate operator+(const Coordinate &lhs, const Coordinate &rhs) {
    Coordinate ret(lhs);
    ret.first += rhs.first;
    ret.second += rhs.second;
    return ret;
}

Location make_location(const Coordinate &lhs, const Coordinate &rhs) {
    return { std::min(lhs, rhs), std::max(lhs, rhs) };
}

Location operator+(const Location &location, const Coordinate &direction) {
    return make_location(location.first + direction, location.second + direction);
}

int solution(std::vector<std::vector<int>> board) {
    const size_t N = board.size();
    const Coordinate GOAL = { N - 1, N - 1 };
    std::set<Location> visited;
    std::queue<std::pair<Location, size_t>> queue;

    auto movable = [&] (const Location &location) {
        const auto &[ coordinate1, coordinate2 ] = location;
        const auto [ r1, c1 ] = coordinate1;
        const auto [ r2, c2 ] = coordinate2;

        return (
            (0 <= r1 && r1 < N && 0 <= c1 && c1 < N) &&
            (0 <= r2 && r2 < N && 0 <= c2 && c2 < N) &&
            (board[r1][c1] == 0 && board[r2][c2] == 0)
        );
    };

    visited.insert(Location({ 0, 0 }, { 0, 1 }));
    queue.push({ Location({ 0, 0 }, { 0, 1 }), 0 });
    while (!queue.empty()) {
        const auto [ current, time ] = queue.front(); queue.pop();
        const auto &[ coordinate1, coordinate2 ] = current;

        if (coordinate2 == GOAL) {
            return time;
        }

        for (size_t k = 0; k < 4; k++) {
            const auto &next = current + OFFSETS[k];

            if (movable(next) && visited.count(next) == 0) {
                visited.insert(next);
                queue.push({ next, time + 1 });
            }
        }

        for (const auto &direction: coordinate1.first == coordinate2.first ? VERTICAL : HORIZONTAL) {
            const auto &to_move = current + OFFSETS[direction];
            const auto &[ candidate1, candidate2 ] = to_move;

            for (const auto &rotated: { make_location(candidate1, coordinate1), make_location(candidate2, coordinate2) }) {
                if (movable(to_move) && visited.count(rotated) == 0) {
                    visited.insert(rotated);
                    queue.push({ rotated, time + 1 });
                }
            }
        }
    }

    return -1;
}

[프로그래머스] 60063 블록 이동하기 (C/C++)

문제

풀이

메모

소스 코드

Share this post