[Lv.3] 블록이동하기

문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

구현해야 할 조건

삼성 문제와 매우 유사한 시뮬레이션 구현이다. 그리고 생각할게 은근히 있는 문제이다. 총 3가지로 나눌 수 있다.
또한 반복적인 방문은 시간초과를 초래할 수 있기 때문에, 방문한 부분을 체크하는 것이 중요하다! visited배열을 3차원 배열로 만들어 표현했다. 현재 위치에서 4방향중 하나로 방문을 한적이 있는지 체크, 이것을 사용하기 위해서는 돌리는 기준점을 정해줘야 한다. 나는 (0,0)을 기준으로 정했다.

1. 단순히 4방향으로 이동 : 이부분은 벽의 유무, 범위를 벗어나지 않는 지를 체크해야한다.

2. (0,0),(0,1)을 가정했을 때 (0,0)을 기준으로 90도 회전 : 90도 회전하면서 범위를 벗어나거나, 벽을 마주하는지 체크해야하고, 기준점을 (0,0)으로 설정했기 때문에, 방향을 바꿔줄 필요가 없다. 

3.(0,0),(0,1)을 가정했을 때 (0,1)을 기준으로 90도 회전 : 90도 회전하면서 범위를 벗어나거나, 벽을 마주하는지 체크 하지만, 방향의 기준을 (0,1)로 설정했기 때문에, 방향을 바꿔서 생각해야한다. (0,1)을 기준으로 돌린 후 (0,0)을 기준으로 visitied배열을 체크해줘야하는 생각이 필요하다. 이 점을 해주지 않으면 문제 해결이 되지 않는다!

아마 시험에 이 문제가 나오게 되면 풀지는 못할 것 같다. 이해하고 문제를 푸는데 너무 오랜시간이 걸린다.

code

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

#define MAX 101
using namespace std;

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1}; // right, down, left, up

const int rdx[4] = {1,1,-1,-1};
const int rdy[4] = {-1,1,1,-1}; // 헷갈리네? 

typedef struct{
    int y;
    int x;
    int dir;
    int time;
}Robot;

int n;
bool visited[MAX][MAX][4];

bool range(int x,int y, int x2, int y2)
{
    if(x < 0 || x >= n || y < 0 || y >= n) return false;
	if(x2 < 0 || x2 >= n || y2 < 0 || y2 >= n) return false;
	
	return true;
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    
    //초기 시작 위치 (0,0), dir = right, time = 0;
    
    queue<Robot> q;
    q.push({0,0,0,0}); // y,x,dir,time
    visited[0][0][0] = true;
    n = board.size();
    int destX = n - 1;
    int destY = n - 1;
    
    while(!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int dir = q.front().dir;
        int time = q.front().time;
        
        q.pop();
        
        int ry = y + dy[dir];
        int rx = x + dx[dir]; // 현재 위치와 4방향중 하나의 로봇의 위치
                
        //end point 종료조건
        if(y == destY && x == destX) return time;
        if(ry == destY && rx == destX) return time; 
        
        int nx,ny,nrx,nry;
        //4방향으로 움직일수 있는 지 확인
        for(int d = 0; d < 4; d++)
        {
            nx = x + dx[d];
            ny = y + dy[d];
            nrx = rx + dx[d];
            nry = ry + dy[d];
            
            //범위 또는 벽이 있는지 확인
            if(!range(nx,ny,nrx,nry) || visited[ny][nx][dir] || board[ny][nx] == 1 || board[nry][nrx] == 1) continue;
            
            visited[ny][nx][dir] = true;
            q.push({ny,nx,dir,time+1});
        }
        
        //첫번째 로봇(왼편기준) 90도 이동
        for(int i = 1; i < 4; i+=2)
        {
            int rotate_dir = (dir + i) % 4; // 90도 회전 위 아래, 좌우,
            
            nrx = x + dx[rotate_dir];
            nry = y + dy[rotate_dir];
            
            int fry,frx;
            
            //시계방향
            if(i == 1)
            {
                fry = y + rdy[rotate_dir];
                frx = x + rdx[rotate_dir];
            }
            else // 반시계
            {
                fry = y + rdy[dir];
                frx = x + rdx[dir];
            }
            
            if(!range(frx,fry,nrx,nry) || visited[y][x][rotate_dir] || board[nry][nrx] == 1 || board[fry][frx] == 1) continue;
            
            visited[y][x][rotate_dir] = true;
            q.push({y,x,rotate_dir,time+1});
        }
        
        //두번째 이동
        
        dir = (dir + 2) % 4;
        
        cout << "dir : " << dir << endl; 
        for(int i = 1; i < 4; i+=2)
        {
            
            int rotate_dir = (dir + i) % 4;
            ny = ry + dy[rotate_dir];
            nx = rx + dx[rotate_dir];
            
            cout << "rotate_dir : " << rotate_dir << endl;
            
            int srx,sry;
            
            if(i == 1) // 시계방향
            {
                srx = rx + rdx[rotate_dir];
                sry = ry + rdy[rotate_dir];
            }
            else // 반시계방향
            {
                srx = rx + rdx[dir];
                sry = ry + rdy[dir];
            }
            
            if(!range(nx,ny,srx,sry) || board[ny][nx] == 1 || board[sry][srx] == 1) continue;
            
            rotate_dir = (rotate_dir + 2) % 4; // 하나 기준으로 visited를 시작해야한다.
            if(visited[ny][nx][rotate_dir]) continue;
            
            //cout << "change rotate_dir : " << rotate_dir << endl;
            visited[ny][nx][rotate_dir] = true;
            q.push({ny,nx,rotate_dir,time+1});
        }
    }
}