[프로그래머스/C++] 블록 이동하기 (2020 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 풀이만 생각하면 그렇게 어렵지 않은 문제다.

가장 빠르게 도달하는 방법을 찾는 문제이므로, BFS로 문제를 해결하면 된다.

 

4방향으로 이동하는 경우와, 회전하는 경우를 고려하면 되는데, 문제는 회전을 구현하는게 생각보다 힘들었다.

 

푸는 방법은 로봇이 가로일 경우, 세로일 경우가 있으므로 visitedHorizontal, visitedVertical 두 2차원 벡터를 이용해 이미 방문 한적이 있는지를 판단하고, 방문했다면 Queue에 넣지 않기로 했다.

 

여기서 일반적인 이동은 Horizontal 방향이면 visitedHorizontal에서 방문한 적이 있는지 확인하면 되는데, 회전할 경우 Horizontal 방향이였으면 Vertical 방향의 2차원 벡터에서 방문한 적이 있는지 확인해야했다.

 

그리고 방문의 기준을 판단해야 했는데, 항상 로봇의 좌 상단이 방문의 기준이 되도록 했다.

 

예를 들어 회전해서 로봇의 가장 좌 상단의 위치가 바꼈다면, 바뀐 좌 상단의 위치를 기준으로 visited에 방문 표시를 한 것이다.

 

이렇게 일반적인 움직임과 회전을 전부 구현한 다음 BFS를 이용해 가장 빠른 경우를 탐색하고 그때의 움직인 수를 return 했다.

 

​

[아이디어 정리]

1. 로봇의 가장 좌 상단을 기준으로 방문 표시를 한다.
2. 방문 표시를 할 벡터를 세로방향 가로방향으로 나눠서 방문했는지 확인한다.
3. 4방향 움직임과 회전을 구현하고, 이를 이용해 BFS로 가장 적게 움직인 수를 return했다.

 

 

Code

 

 

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

struct robot
{
    int y;
    int x;
    int moveCnt;
    bool isH; //Horizon    
};

int dy[4]={0,1,-1,0};
int dx[4]={1,0,0,-1};
// 수직 오른쪽 한칸, 왼쪽 한칸, 오른쪽 한칸, 왼쪽 한칸
// 평행 아래 한칸, 위 한칸 ,아래 한칸, 위 한칸

// 회전가능한지 검사
bool CanRotate(int y, int x, int dir, vector<vector<int>>&board)// dir == 상하좌우
{
    //상 y-1, x+1, 하 y+1 x+1 좌 y+1, x-1 우 y+1, x+1
    int rry[4]={-1,1,1,1};
    int rrx[4]={1,1,-1,1};   
    int ay, ax;
    for (int i=0; i<2; i++)
    {
        for (int j=0; j<2; j++)
        {
            ay=y+rry[dir]*i, ax=x+rrx[dir]*j;
            if(0<=ay&&ay<board.size() && 0<=ax&&ax<board[0].size())
            {
                if (board[ay][ax]==1)
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
    }
    return true;
}


int BFS(vector<vector<int>> &board)
{
    int by=board.size(), bx=board[0].size();
    vector<vector<bool>> visitedH(by, vector<bool>(bx,false));
    vector<vector<bool>> visitedV(by, vector<bool>(bx,false));
    robot r, nowR;
    r.y=0,r.x=0,r.isH=true,r.moveCnt=0;
    queue<robot> q; //항상 좌상단 기준
    q.push(r);
    int ny, nx;
    visitedH[0][0]=true;
    while (!q.empty())
    {
        nowR = q.front();
        q.pop();
        if (nowR.isH)
        {
            if (nowR.y==by-1&& (nowR.x==bx-1||nowR.x==bx-2))
            {
                return nowR.moveCnt;
            }
        }
        else
        {
            if ((nowR.y==by-2||nowR.y==by-1)&& nowR.x==bx-1)
            {
                return nowR.moveCnt;
            }
        }
        
        for (int i=0; i<4; i++)
        {
            ny=nowR.y+dy[i];
            nx=nowR.x+dx[i];
            if (nowR.isH)
            {
                if (ny>=0 &&ny<by&& nx>=0 &&nx<bx-1) // 가로로 한칸 더 길기 때문
                {
                    if (!visitedH[ny][nx]&&board[ny][nx]==0&&board[ny][nx+1]==0)
                    {
                        visitedH[ny][nx]=true;
                        r.y=ny,r.x=nx,r.moveCnt=nowR.moveCnt+1,r.isH=nowR.isH;
                        q.push(r);
                    }
                }
            }
            else
            {
                if (ny>=0 &&ny<by-1&& nx>=0 &&nx<bx) // 세로로 한칸 더 길기 때문
                {
                    if (!visitedV[ny][nx]&&board[ny][nx]==0&&board[ny+1][nx]==0)
                    {
                        visitedV[ny][nx]=true;
                        r.y=ny,r.x=nx,r.moveCnt=nowR.moveCnt+1,r.isH=nowR.isH;
                        q.push(r);
                    }
                }
            }
        }
        // 회전
        if (nowR.isH)
        {
            // 왼쪽 기준 회전, 오른쪽기준회전 //0,1 상 하
            for (int i=0; i<2; i++)
            {
                if (CanRotate(nowR.y,nowR.x, i,board))
                {
                    if (i==0)
                    { //왼상, 오상
                        if (!visitedV[nowR.y-1][nowR.x])
                        {
                            visitedV[nowR.y-1][nowR.x]=true;
                            r.y=nowR.y-1, r.x=nowR.x, r.isH=false, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                        if (!visitedV[nowR.y-1][nowR.x+1])
                        {
                            visitedV[nowR.y-1][nowR.x+1]=true;
                            r.y=nowR.y-1, r.x=nowR.x+1, r.isH=false, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                    }
                    else
                    {   //왼하 오하
                        if (!visitedV[nowR.y][nowR.x])
                        {
                            visitedV[nowR.y][nowR.x]=true;
                            r.y=nowR.y, r.x=nowR.x, r.isH=false, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                        if (!visitedV[nowR.y][nowR.x+1])
                        {
                            visitedV[nowR.y][nowR.x+1]=true;
                            r.y=nowR.y, r.x=nowR.x+1, r.isH=false, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                    }
                }
            }
        }
        else
        {
            for (int i=2; i<4; i++)
            {
                if (CanRotate(nowR.y,nowR.x, i,board))
                {
                    if (i==2)
                    { //좌, 좌하
                        if (!visitedH[nowR.y][nowR.x-1])
                        {
                            visitedH[nowR.y][nowR.x-1]=true;
                            r.y=nowR.y, r.x=nowR.x-1, r.isH=true, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                        if (!visitedH[nowR.y+1][nowR.x-1])
                        {
                            visitedH[nowR.y+1][nowR.x-1]=true;
                            r.y=nowR.y+1, r.x=nowR.x-1, r.isH=true, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                    }
                    else
                    {   //우, 우하
                        if (!visitedH[nowR.y][nowR.x])
                        {
                            visitedH[nowR.y][nowR.x]=true;
                            r.y=nowR.y, r.x=nowR.x, r.isH=true, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                        if (!visitedH[nowR.y+1][nowR.x])
                        {
                            visitedH[nowR.y+1][nowR.x]=true;
                            r.y=nowR.y+1, r.x=nowR.x, r.isH=true, r.moveCnt=nowR.moveCnt+1;
                            q.push(r);
                        }
                    }
                }
            }
        }
    }
    return -1;
}


int solution(vector<vector<int>> board) {
    int answer=BFS(board);
    return answer;
}

 

---

 

정말로 문제 자체는 어렵지 않았는데, 회전이 문제였다. 

로봇이 두 팔을 기준으로 전부 회전이 가능했고, 회전하는 경우에 따라 로봇의 좌상단이 바뀌기 때문에 이 경우를 전부 기록하는게 힘들었다.

특히 중간에 +를 -로 잘못 적은 부분 때문에 눈이 빠지는 줄;;

 

프로그래머스