[C++] 프로그래머스 - 블록 이동하기

2020 KAKAO BLIND RECRUITMENT (2020 카카오 블라인드 채용 문제)

 

N * N 의 보드에서 로봇을 N * N의 위치로 몇초만에 이동 시킬 수 있는지 찾는 문제입니다.

로봇은 상하좌우로 이동할 수 있습니다.
회전은 하는 중에 벽이 걸리지 않으면 회전이 가능합니다.

1초에 움직일 수 있는 모든 경우의 수를 확인해보았습니다.

1. 위로 이동
2. 오른쪽 이동
3. 왼쪽 이동
4. 아래 이동

5. 왼쪽을 축으로 위로 90도 회전(로봇이 가로인 상태)
6. 오른쪽을 축으로 위로 90도 회전(로봇이 가로인 상태)
7. 왼쪽을 축으로 아래로 90도 회전(로봇이 가로인 상태)
8. 오른쪽을 축으로 아래로 90도 회전(로봇이 가로인 상태) 

9. 위를 축으로 왼쪽으로 90도 회전(로봇이 세로인 상태)
10. 위를 축으로 오른쪽으로 90도 회전(로봇이 세로인 상태)
11. 아래를 축으로 왼쪽으로 90도 회전(로봇이 세로인 상태)
12. 아래를 축으로 오른쪽으로 90도 회전(로봇이 세로인 상태) 

1~4의 경우
1. 보드를 벗어나는지 확인
2. 이동하는 방향에 벽이 있는지 확인

5~12의 경우
1. 보드를 벗어나는지 확인
2. 회전을 하는 사각형에 벽이 있는지 확인

위의 경우를 처리해준 다음에 BFS를 통해 도착지점을 찾을때까지 탐색합니다.
check배열을 통해 동일한부분을 탐색할때 더 오랜 시간이 걸린 경우 탐색을 스킵합니다.

도착지점을 찾게되었을때 시간을 출력합니다.
로봇이 도착하는 경우만 문제로 나오기때문에 이부분을 따로 예외처리해줄 필요는 없습니다.

 

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

int area;
int check[100][100][2] = {10000};
int direction[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
};
int spin[2][4][2] = {
    {{-1, 0}, {-1, 1}, {0, 0}, {0, 1}},
    {{0, -1}, {1, -1}, {0, 0}, {1, 0}},
};

bool checkArae(int y, int x, int d, vector<vector<int>> board)
{
  if (y < 0 || (d == 0 && y >= area) || (d == 1 && y + 1 >= area))
  {
    return false;
  }
  if (x < 0 || (d == 0 && x + 1 >= area) || (d == 1 && x >= area))
  {
    return false;
  }
  if (board[y][x] == 1 || (d == 0 && board[y][x + 1] == 1) || (d == 1 && board[y + 1][x] == 1))
  {
    return false;
  }
  return true;
}

int solution(vector<vector<int>> board)
{
  queue<vector<int>> q;
  area = board.size();

  fill(check[0][0], check[100][0], 10000);
  check[0][0][0] = 0;

  q.push({0, 0, 0, 0});

  while (!q.empty())
  {
    int y = q.front()[0];
    int x = q.front()[1];
    int d = q.front()[2];
    int c = q.front()[3];

    q.pop();

    for (int i = 0; i < 4; ++i)
    {
      int moveY = y + direction[i][0];
      int moveX = x + direction[i][1];
      int moveC = c + 1;
      if (!checkArae(moveY, moveX, d, board))
      {
        continue;
      }
      if (check[moveY][moveX][d] <= c)
      {
        continue;
      }
      check[moveY][moveX][d] = moveC;
      if ((d == 0 && moveX == area - 2 && moveY == area - 1) || (d == 1 && moveX == area - 1 && moveY == area - 2))
      {
        return moveC;
      }
      q.push({moveY, moveX, d, moveC});
    }
    for (int i = 0; i < 4; ++i)
    {
      int spinY = spin[d][i][0] + y;
      int spinX = spin[d][i][1] + x;
      int spinD;
      int spinC = c + 1;
      if (d == 0)
      {
        int spinD = 1;

        if (i < 2 && (!checkArae(y, x, 0, board) || !checkArae(y - 1, x, 0, board)))
        {
          continue;
        }
        if (i >= 2 && (!checkArae(y, x, 0, board) || !checkArae(y + 1, x, 0, board)))
        {
          continue;
        }
        if (check[spinY][spinX][spinD] <= spinC)
        {
          continue;
        }
        check[spinY][spinX][spinD] = spinC;
        if ((spinD == 0 && spinX == area - 2 && spinY == area - 1) || (spinD == 1 && spinX == area - 1 && spinY == area - 2))
        {
          return spinC;
        }
        q.push({spinY, spinX, spinD, spinC});
      }
      else
      {
        int spinD = 0;

        if (i < 2 && (!checkArae(y, x - 1, 0, board) || !checkArae(y + 1, x - 1, 0, board)))
        {
          continue;
        }
        if (i >= 2 && (!checkArae(y, x, 0, board) || !checkArae(y + 1, x, 0, board)))
        {
          continue;
        }
        if (check[spinY][spinX][spinD] <= spinC)
        {
          continue;
        }
        check[spinY][spinX][spinD] = spinC;
        if ((spinD == 0 && spinX == area - 2 && spinY == area - 1) || (spinD == 1 && spinX == area - 1 && spinY == area - 2))
        {
          return spinC;
        }
        q.push({spinY, spinX, spinD, spinC});
      }
    }
  }

  return 0;
}