[1일 1알고] 블록 이동하기

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

프로그래머스

소위 말하자면 빡구현 문제입니다.

 

기본적으로 2차원 NxN 배열 내에서 벽을 피해가는 문제이며 최단거리로 이동해야하기 때문에 BFS계열 탐색을 사용해야합니다.

 

이 문제의 특징으로는 이동하는 주체인 로봇이 2x1 크기라는 것이고, 회전이 가능하다는 점입니다.

 

따라서 이동의 처리는 상하좌우 4방 + 회전의 경우를 고려하며 가로와 세로를 별도로 생각해야합니다.

---

가로와 세로에 대한 거리 측정을 3차원 배열로 묶어서 처리할 수도 있겠지만 저는 가로, 세로를 각각 담당하는 2차원 배열을 만들어서 처리했습니다. 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

// 2x1크기의 로봇
// 회전은 축을 중심으로 이루어짐
// 이동과 회전의 시간은 같음
int N;

struct Status
{
    int r, c;
    bool isGaro;
};

bool check(int r1, int c1, int r2, int c2, vector<vector<int>>& board)
{
    if (r1 < 0 || r2 < 0 || r1 >= N || r2 >= N ||
        c1 < 0 || c2 < 0 || c1 >= N || c2 >= N ||
        board[r1][c1] == 1 || board[r2][c2] == 1)
    {
        return false;
    }
    return true;
}

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

    N = board.size();

    vector<vector<int>> garodist(N, vector<int>(N, -1));
    vector<vector<int>> serodist(N, vector<int>(N, -1));

    garodist[0][0] = 0;

    queue<Status> q;
    q.push({ 0, 0, true });

    int dr[4] = { -1, 0, 1, 0 };
    int dc[4] = { 0, -1, 0, 1 };

    while (!q.empty())
    {
        auto[r1, c1, isGaro] = q.front();
        q.pop();
        int r2, c2;
        if (isGaro)
        {
            r2 = r1;
            c2 = c1 + 1;
        }
        else
        {
            r2 = r1 + 1;
            c2 = c1;
        }
        // 4방 이동의 경우
        for (int i = 0; i < 4; ++i)
        {
            int nr1 = r1 + dr[i];
            int nc1 = c1 + dc[i];
            int nr2 = r2 + dr[i];
            int nc2 = c2 + dc[i];
            if (check(nr1, nc1, nr2, nc2, board))
            {
                if (isGaro && garodist[nr1][nc1] == -1)
                {
                    garodist[nr1][nc1] = garodist[r1][c1] + 1;
                    q.push({ nr1, nc1, isGaro });
                }
                else if (!isGaro && serodist[nr1][nc2] == -1)
                {
                    serodist[nr1][nc1] = serodist[r1][c1] + 1;
                    q.push({ nr1, nc1, isGaro });
                }
            }
        }
        
        // 회전의 경우
        for (int i = 0; i < 4; ++i)
        {
            if (isGaro)
            {
                // 가로에서 밑으로 회전
                if (check(r1 + 1, c1, r2 + 1, c2, board))
                {
                    if (serodist[r1][c1] == -1)
                    {
                        serodist[r1][c1] = garodist[r1][c1] + 1;
                        q.push({ r1, c1, !isGaro });
                    }

                    if (serodist[r2][c2] == -1)
                    {
                        serodist[r2][c2] = garodist[r1][c1] + 1;
                        q.push({ r2, c2, !isGaro });
                    }
                }

                // 가로에서 위로 회전
                if (check(r1 - 1, c1, r2 - 1, c2, board))
                {
                    if (serodist[r1 - 1][c1] == -1)
                    {
                        serodist[r1 - 1][c1] = garodist[r1][c1] + 1;
                        q.push({ r1 - 1, c1, !isGaro });
                    }

                    if (serodist[r2 - 1][c2] == -1)
                    {
                        serodist[r2 - 1][c2] = garodist[r1][c1] + 1;
                        q.push({ r2 - 1, c2, !isGaro });
                    }
                }
            }
            else
            {
                // 세로에서 좌로 회전
                if (check(r1, c1 - 1, r2, c2 - 1, board))
                {
                    if (garodist[r1][c1 - 1] == -1)
                    {
                        garodist[r1][c1 - 1] = serodist[r1][c1] + 1;
                        q.push({ r1, c1 - 1, !isGaro });
                    }

                    if (garodist[r2][c2 - 1] == -1)
                    {
                        garodist[r2][c2 - 1] = serodist[r1][c1] + 1;
                        q.push({ r2, c2 - 1, !isGaro });
                    }
                }

                // 세로에서 우로 회전
                if (check(r1, c1 + 1, r2, c2 + 1, board))
                {
                    if (garodist[r1][c1] == -1)
                    {
                        garodist[r1][c1] = serodist[r1][c1] + 1;
                        q.push({ r1, c1, !isGaro });
                    }
                    if (garodist[r2][c2] == -1)
                    {
                        garodist[r2][c2] = serodist[r1][c1] + 1;
                        q.push({ r2 , c2, !isGaro });
                    }
                }
            }
        }
    }
    
    if (garodist[N - 1][N - 2] == -1)
    {
        answer = serodist[N - 2][N - 1];
    }
    else if (serodist[N - 2][N - 1] == -1)
    {
        answer = garodist[N - 1][N - 2];
    }
    else
    {
        answer = min(garodist[N - 1][N - 2], serodist[N - 2][N - 1]);
    }

    return answer;
}

 

결국 문제는 한번 틀리면 돌이킬 수 없기 때문에 

이러한 기본적인 문제는 더더욱 범위확인, 예외처리 등에 주의해야할 것입니다.