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

문제 설명

로봇 개발자무지는 한 달 앞으로 다가온 카카오배 로봇 경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 0은 빈칸을 1은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분 없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초입니다.

0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

 

입출력 예

board	result
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]	7

 

 

코드

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

using namespace std;

struct pos
{
    int a;  // y1
    int b;  // x1
    int c;  // y2
    int d;  // x2
    int r;  // 가로 : 0, 세로 : 1
    
    void init(int a, int b, int c, int d, int r)
    {
        this->a = a;
        this->b = b;
        this->c = c;
        this->d = d;
        this->r = r;
    }
};

int N;                      // 지도의 크기
int m[101][101][2];         // 각 위치에 도착하기 위한 최소 시간 + 1
int d[] = {-1, 1, 0, 0};    // 이동하기 (위-아래-오른쪽-왼쪽)

// 목적지에 도착했는지 확인
bool is_dest(pos p)
{
    if (p.a == N && p.b == N - 1 && p.r == 0)
    {
        return true;
    }
    if (p.a == N - 1 && p.b == N && p.r == 1)
    {
        return true;
    }
    return false;
}

// 조건을 검사하고 현재 위치를 큐에 삽입
void push_pos(queue<pos> &q, pos p, int dist)
{
    // 아직 도착한 적이 없는 경우에만 수행
    // 이미 도착한 적이 있다면 그 때의 시간이 최소 시간임
    if (!m[p.a][p.b][p.r])
    {
        q.push(p);
        m[p.a][p.b][p.r] = dist + 1;
    }
}

int bfs(vector<vector<int>> &board)
{
    queue<pos> q;
    pos curr, next;
    int i, dist;
    
    // 출발지를 큐에 삽입하고 최소 시간을 1로 저장
    next.init(1, 1, 1, 2, 0);
    q.push(next);
    m[next.a][next.b][next.r] = 1;
    while (!q.empty())
    {
        curr = q.front();
        q.pop();
        dist = m[curr.a][curr.b][curr.r];
        // (N, N)에 도착한 경우
        if (is_dest(curr))
        {
            return dist - 1;
        }
        // 이동하기
        for (i = 0; i < 4; i++)
        {
            next.init(curr.a + d[i], curr.b + d[3 - i], curr.c + d[i], curr.d + d[3 - i], curr.r);
            // 지도의 범위를 벗어나지 않는 경우
            if (next.a >= 1 && next.c <= N && next.b >= 1 && next.d <= N)
            {
                // 로봇이 위치한 두 칸 모두 빈칸인 경우
                if (!board[next.a - 1][next.b - 1] && !board[next.c - 1][next.d - 1])
                {
                    push_pos(q, next, dist);
                }
            }
        }
        // 회전하기 (가로 -> 세로)
        if (curr.r == 0)
        {
            // 위쪽으로 회전
            if (curr.a > 1 && !board[curr.a - 2][curr.b - 1] && !board[curr.c - 2][curr.d - 1])
            {
                // (a, b) 기준 반시계 방향
                next.init(curr.a - 1, curr.b, curr.a, curr.b, !curr.r);
                push_pos(q, next, dist);
                // (c, d) 기준 시계 방향
                next.init(curr.c - 1, curr.d, curr.c, curr.d, !curr.r);
                push_pos(q, next, dist);
            }
            // 아래쪽으로 회전
            if (curr.c < N && !board[curr.a][curr.b - 1] && !board[curr.c][curr.d - 1])
            {
                // (a, b) 기준 시계 방향
                next.init(curr.a, curr.b, curr.a + 1, curr.b, !curr.r);
                push_pos(q, next, dist);
                // (c, d) 기준 반시계 방향
                next.init(curr.c, curr.d, curr.c + 1, curr.d, !curr.r);
                push_pos(q, next, dist);
            }
        }
        // 회전하기 (세로 -> 가로)
        else
        {
            // 왼쪽으로 회전
            if (curr.b > 1 && !board[curr.a - 1][curr.b - 2] && !board[curr.c - 1][curr.d - 2])
            {
                // (a, b) 기준 시계 방향
                next.init(curr.a, curr.b - 1, curr.a, curr.b, !curr.r);
                push_pos(q, next, dist);
                // (c, d) 기준 반시계 방향
                next.init(curr.c, curr.d - 1, curr.c, curr.d, !curr.r);
                push_pos(q, next, dist);
            }
            // 오른쪽으로 회전
            if (curr.d < N && !board[curr.a - 1][curr.b] && !board[curr.c - 1][curr.d])
            {
                // (a, b) 기준 반시계 방향
                next.init(curr.a, curr.b, curr.a, curr.b + 1, !curr.r);
                push_pos(q, next, dist);
                // (c, d) 기준 시계 방향
                next.init(curr.c, curr.d, curr.c, curr.d + 1, !curr.r);
                push_pos(q, next, dist);
            }
        }
    }
    return 0;
}

int solution(vector<vector<int>> board)
{
    int answer;

    N = board.size();
    answer = bfs(board);
    return answer;
}

 

로봇이 목적지에 도착하는 경우의 로봇의 좌표를 (y, x)로 나타내면 다음과 같다.

1. 가로일 때 : (N, N - 1) (N, N)
2. 세로일 때 : (N - 1, N) (N, N)

따라서 is_dest() 함수에서는 위의 기준을 가지고 목적지에 도착했는지를 확인한다.

배열 m[a][b][r]은 각 좌표에 도착하기 위한 최소 시간 + 1을 저장한다. 이때,  1을 더하는 이유는 확인되지 않은 경우를 구분하기 위해서이다. 배열 m은 전역 변수이므로 0으로 초기화되는데, 출발지의 최소 시간도 0이다. 따라서 둘을 구분할 수 없기 때문에 1을 더해서 저장하고, 목적지에 도착한 경우 1을 빼서 리턴한다.

탐색은 bfs를 사용했다. 로봇은 지도의 범위 내에서 빈칸만 사용해서 상하좌우로 움직이거나 각 좌표를 기준으로 시계/반시계 방향으로 회전할 수 있다. 이렇게 이동할 수 있는 모든 경우를 확인하며 최초로 목적지에 도착하는 순간이 최소 시간이므로 즉시 결과를 리턴한다.

 

링크

programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

github.com/inbdni/Programmers/blob/master/level03/%EB%B8%94%EB%A1%9D%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0.cpp

inbdni/Programmers