문제 설명

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

블럭이동-1.jpg

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

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

블럭이동-2.jpg

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

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

제한사항

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

입출력 예

boardresult
[[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

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

문제 요약

board가 주어지고 로봇은 처음 위치 (0,0) (0,1)에 위치 해 있다.
로봇을 최소 시간으로 (N-1, N-1) 로 이동시키면 된다.

문제 풀이

도착까지 최소 시간을 구하는 문제로 bfs 를 이용하면 된다.
로봇이 2칸을 차지하기 때문에 어느 한 기준점을 정하는게 좋은데
왼쪽 위를 기준으로 vertical, horizontal 상태를 체크해서 중복을 방지했다.

문제에서 따로 언급이 없었지만 회전이동이 아닌 평행이동도 가능하다는 것을 명심하자

소스 코드

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

using namespace std;

const int HORIZONTAL = 0;
const int VERTICAL = 1;

bool visited[100][100][2];
vector<vector<int>> map;
int N;

struct Pos {
    int y, x, state, dist;
};

bool isFinish(Pos& pos) {
    if (pos.y == N-1 && pos.x == N-2 && pos.state == HORIZONTAL) return true;
    if (pos.y == N-2 && pos.x == N-1 && pos.state == VERTICAL) return true;
    return false;
}
bool isRoad(int y, int x) {
    if (y < 0 || x < 0 || y >= N || x >= N) return false;
    if (map[y][x] == 1) return false;
    return true;
}
vector<Pos> next(Pos& pos)
{
    vector<Pos> nextPos;
    if (pos.state == HORIZONTAL) {
        if (isRoad(pos.y-1, pos.x) && isRoad(pos.y-1, pos.x+1)){
            nextPos.push_back({pos.y-1, pos.x, VERTICAL, pos.dist+1});
            nextPos.push_back({pos.y-1, pos.x+1, VERTICAL, pos.dist+1});
            nextPos.push_back({pos.y-1, pos.x, HORIZONTAL, pos.dist+1});
        }
        if (isRoad(pos.y+1, pos.x) && isRoad(pos.y+1, pos.x+1)){
            nextPos.push_back({pos.y, pos.x, VERTICAL, pos.dist+1});
            nextPos.push_back({pos.y, pos.x+1, VERTICAL, pos.dist+1});
            nextPos.push_back({pos.y+1, pos.x, HORIZONTAL, pos.dist+1});
        }
        if (isRoad(pos.y, pos.x+2)){
            nextPos.push_back({pos.y, pos.x+1, HORIZONTAL, pos.dist+1});
        }
        if (isRoad(pos.y, pos.x-1)){
            nextPos.push_back({pos.y, pos.x-1, HORIZONTAL, pos.dist+1});
        }
    } else {
        if (isRoad(pos.y, pos.x+1) && isRoad(pos.y+1, pos.x+1)){
            nextPos.push_back({pos.y, pos.x, HORIZONTAL, pos.dist+1});
            nextPos.push_back({pos.y+1, pos.x, HORIZONTAL, pos.dist+1});
            nextPos.push_back({pos.y, pos.x+1, VERTICAL, pos.dist+1});
        }
        if (isRoad(pos.y, pos.x-1) && isRoad(pos.y+1, pos.x-1)){
            nextPos.push_back({pos.y, pos.x-1, HORIZONTAL, pos.dist+1});
            nextPos.push_back({pos.y+1, pos.x-1, HORIZONTAL, pos.dist+1});
            nextPos.push_back({pos.y, pos.x-1, VERTICAL, pos.dist+1});
        }
        if (isRoad(pos.y-1, pos.x)){
            nextPos.push_back({pos.y-1, pos.x, VERTICAL, pos.dist+1});
        }
        if (isRoad(pos.y+2, pos.x)){
            nextPos.push_back({pos.y+1, pos.x, VERTICAL, pos.dist+1});
        }
    }
    return nextPos;
}
int bfs(){
    queue<Pos> q;
    q.push({0,0,HORIZONTAL,0});

    while(!q.empty()) {
        auto pos = q.front();
        q.pop();

        if (isFinish(pos)) return pos.dist;
        
        auto& v = visited[pos.y][pos.x][pos.state];
        if (v) continue;
        v = true;

        auto nextPos = next(pos);
        for(auto& newPos : nextPos){
            q.push(newPos);
        }
    }
    return 0;
}

int solution(vector<vector<int>> board) {
    map = board;
    N = board.size();
    return bfs();
}

문제 위치 – https://programmers.co.kr/learn/courses/30/lessons/60063