[level 3] 블록 이동하기 - 60063

문제 링크

성능 요약

메모리: 4.69 MB, 시간: 1.54 ms

구분

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT

문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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

입출력 예에 대한 설명

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

코드

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

// 방향 정의
const int dx[] = {0, 1, -1, 0};
const int dy[] = {1, 0, 0, -1};

// 회전 방향 정의
const int rot[2][5][2] = {
    {{0, 0}, {0, 0}, {0, 1}, {-1, 0}, {-1, 1}},
    {{0, 0}, {0, 0}, {1, 0}, {0, -1}, {1, -1}}
};

struct State {
    int count, x1, y1, d;
};

int solution(vector<vector<int>> board) {
    int n = board.size();
    int answer = 0;

    // 방문 여부 및 방향에 따른 상태 저장
    vector<vector<vector<int>>> visited(n, vector<vector<int>>(n, vector<int>(2, 0)));

    // count, x1, y1, d
    deque<State> q;
    q.push_back({0, 0, 0, 0});

    while (!q.empty()) {
        auto [count, x1, y1, d] = q.front();
        q.pop_front();

        int x2 = x1 + dx[d];
        int y2 = y1 + dy[d];


        if ((x1 == n - 1 && y1 == n - 1) || (x2 == n - 1 && y2 == n - 1)) {
            answer = count;
            break;
        }

        for (int k = 0; k < 4; ++k) {
            int hx1 = x1 + dx[k];
            int hy1 = y1 + dy[k];
            int hx2 = x2 + dx[k];
            int hy2 = y2 + dy[k];

            if (hx1 >= 0 && hx1 < n && hy1 >= 0 && hy1 < n && hx2 >= 0 && hx2 < n && hy2 >= 0 && hy2 < n) {
                if (board[hx1][hy1] == 0 && board[hx2][hy2] == 0) {
                    //회전X의 경우 : 이동 방향에 벽이 없고 현재 회전방향 상태로 방문한 적이 없다면 추가
                    if(visited[hx1][hy1][d] == 0)
                    {
                        visited[hx1][hy1][d] = 1;
                        q.push_back({count+1, hx1, hy1, d});
                    }
                        
                    //회전O의 경우
                    //가로방향이고 세로축 이동이고 그 방향에 벽이 없다면 해당 방향으로 회전하고 방문 확인
                    if(dx[k] != 0 && d == 0){
                        //dx[k]>0 : 1, 2 | dx[k] <0 : -1, -2
                        int nd = 1;
                        for(int i = 1; i < 3; i++){
                            int next = dx[k] >= 0 ? i * dx[k] : 5 + i * dx[k];
                            int hx = x1 + rot[d][next][0];
                            int hy = y1 + rot[d][next][1];
                            if(visited[hx][hy][nd] == 0){
                                visited[hx][hy][nd] = 1;
                                q.push_back({count+1, hx, hy, nd});
                            }
                        }
                    }
                    //세로방향이고 가로축 이동이고 그 방향에 벽이 없다면 해당 방향으로 회전하고 방문 확인
                    else if(dy[k] != 0 && d == 1)
                    {
                        int nd = 0;
                        for(int i = 1; i < 3; i++)
                        {
                            int next = dy[k] >= 0 ? i * dy[k] : 5 + i * dy[k];
                            int hx = x1 + rot[d][next][0];
                            int hy = y1 + rot[d][next][1];
                            if(visited[hx][hy][nd] == 0)
                            {
                                visited[hx][hy][nd] = 1;
                                q.push_back({count+1, hx, hy, nd});
                            }
                        }
                    }
                }
            }
        }
    }

    return answer;
}

테스트 결과