Programmers 블록 이동하기

2020 KAKAO BLIND RECRUITMENT 문제 중 하나인

블록 이동하기 문제를 풀어봤습니다.

 

막힘없이 코드를 작성하긴 했지만,, 정말 오랜 시간이 걸렸기 때문에

이 문제를 풀면서 제 실력이 어느 수준인지 느낄 수 있었습니다.

 

움직일 수 있는 것은 문제에 주어졌듯이 2가지 형태입니다.

로봇 전체를 동서남북으로 움직이거나 // 둘 중 하나의 축을 기준으로 회전시키는 것입니다.

 

회전을 좀 더 간단하게 구현할 수 있었다면 좋았겠지만

딱히 방법이 떠오르지 않아 노가다로 조건을 주었습니다..

 

 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
struct robot{
    int y,x,side,time;
    /*
    side : 0, 1, 2, 3 // N, E, S, W
    */
};

int N;
int mx[4] = {0,0,-1,1};
int my[4] = {1,-1,0,0};
bool visit[100][100][4];
vector<vector<int> > board;

int getY(int y, int side){return side==0?y-1:(side==1?y:(side==2?y+1:y));}
int getX(int x, int side){return side==0?x:(side==1?x+1:(side==2?x:x-1));}

// ccw true : ccw || ccw false : cw
bool canMove(int y, int x, int side, int ccw){
    if(side==0){
        if(ccw){
            if(x-1>=0&&!board[y-1][x-1]&&!board[y][x-1]&&!visit[y][x][3]) return true;
        }
        else{
            if(x+1<N&&!board[y-1][x+1]&&!board[y][x+1]&&!visit[y][x][1]) return true;
        }
    }
    if(side==1){
        if(ccw){
            if(y-1>=0&&!board[y-1][x+1]&&!board[y-1][x]&&!visit[y][x][0]) return true;
        }
        else{
            if(y+1<N&&!board[y+1][x+1]&&!board[y+1][x]&&!visit[y][x][2]) return true;
        }
    }
    if(side==2){
        if(ccw){
            if(x+1<N&&!board[y+1][x+1]&&!board[y][x+1]&&!visit[y][x][1]) return true;
        }
        else{
            if(x-1>=0&&!board[y+1][x-1]&&!board[y][x-1]&&!visit[y][x][3]) return true;
        }
    }
    if(side==3){
        if(ccw){
            if(y+1<N&&!board[y+1][x-1]&&!board[y+1][x]&&!visit[y][x][2]) return true;   
        }
        else{
            if(y-1>=0&&!board[y-1][x-1]&&!board[y-1][x]&&!visit[y][x][0]) return true;
        }
    }
    return false;
}

int solution(vector<vector<int>> arr) {
    int answer = 0;
    board = arr;
    N = board.size();
    
    queue<robot> q;
    q.push({0,0,1,0});
    while(!q.empty()){
        int fy = q.front().y;
        int fx = q.front().x;
        int side = q.front().side;
        int sy = getY(fy, side);
        int sx = getX(fx, side);
        int time = q.front().time;
        q.pop();
        
        if((fy==N-1 && fx==N-1)||(sy==N-1&&sx==N-1)){
            answer = time;
            break;
        }
        
        if(visit[fy][fx][side]) continue;
        visit[fy][fx][side] = true;
        
        // move E,W,S,N
        for(int i = 0; i<4; i++){
            int ffy = fy+my[i];
            int ffx = fx+mx[i];
            int ssy = sy+my[i];
            int ssx = sx+mx[i];
            if(!(ffy>=0&&ffy<N&&ffx>=0&&ffx<N&&!board[ffy][ffx])) continue;
            if(!(ssy>=0&&ssy<N&&ssx>=0&&ssx<N&&!board[ssy][ssx])) continue;
            if(visit[ffy][ffx][side]) continue;
            q.push({ffy,ffx,side,time+1}); // use side var
        }
        
        // move one point
        // based fy, fx
        if(canMove(fy,fx,side,true)){
            for(int i = 0; i<4; i++){
                if(side == i) q.push({fy,fx,(i+3)%4,time+1});
            }
        }
        if(canMove(fy,fx,side,false)){
            for(int i = 0; i<4; i++){
                if(side==i) q.push({fy,fx,(i+1)%4,time+1});
            }
        }
        // based sy, sx
        if(canMove(sy,sx,(side+2)%4,true)){
            for(int i = 0; i<4; i++){
                if((side+2)%4 == i) q.push({sy,sx,(i+3)%4,time+1});
            }
        }
        if(canMove(sy,sx,(side+2)%4,false)){
            for(int i = 0; i<4; i++){
                if((side+2)%4 == i) q.push({sy,sx,(i+1)%4,time+1});
            }
        }
    }
    
    return answer;
}