블록 이동하기
문제 해석
(1,1)위치에 있는 로봇이 (N,N)까지 도달하기 위한 최소 시간을 구하는 문제입니다.
로봇은 2x1크기로 이루어져있고, 초기에 (1,1)을 기준으로 오른쪽 방향으로 되어있습니다.
로봇은 상하좌우로 이동이 가능하며, 회전 기능을 갖추고 있습니다.
회전을 하는 기준점은 두가지가 있습니다. 해당 기준점을 기준으로 90도 회전을 할 때, 그 위를 지나가는 칸은 모두 비어있어야 합니다.
로봇의 한 끝이라도 (N,N)에 도달하면 됩니다.
설계(30)
약간 까다로운 완전탐색 문제입니다. BFS탐색기법을 이용하여 원하는 답을 구할 수 있습니다.
저의 경우 로봇의 상태를 표현하기 위하여 {x,y,dir}의 정보를 가진 자료구조를 이용하였습니다.
x,y를 기준으로하여 dir방향으로 로봇이 이동해 있다는 것을 표현한 것입니다.
이동하는 경우는 그냥 구현하면 됩니다. 문제는 회전하는 부분입니다.
기준점이 바뀌는 경우도 고려해야하기 때문입니다. 각 기준점에 대해서 시계,반시계 방향 회전을 고려하여 최소거리를 찾습니다.
구현(50)
코드
#include <string>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int dist[101][101][4];
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
struct node {
int x, y, dir;
};
queue<node> q;
bool is_range(int x, int y,vector<vector<int> > board) {
int N = board.size();
if (x < 0 || x >= N || y < 0 || y >= N) return false;
return true;
}
void check(int x,int y,int dir,int mode,int now_dist,vector<vector<int> > board) {
int n_dir;
if (mode == 0) n_dir = (dir + 1) % 4;
else n_dir = (dir+3) % 4;
int nx1 = x + dx[dir];
int ny1 = y + dy[dir];
int nx2 = x + dx[n_dir];
int ny2 = y + dy[n_dir];
int nx3 = x + dx[dir] + dx[n_dir];
int ny3 = y + dy[dir] + dy[n_dir];
if (!is_range(nx1, ny1, board) || !is_range(nx2, ny2, board) || !is_range(nx3, ny3, board)) return;
if (board[nx1][ny1] || board[nx2][ny2] || board[nx3][ny3] || dist[x][y][n_dir]!=-1) return;
dist[x][y][n_dir] = now_dist + 1;
q.push({ x,y,n_dir });
}
int solution(vector<vector<int>> board) {
memset(dist, -1, sizeof(dist));
int N = board.size();
q.push({ 0,0,0 });
dist[0][0][0] = 0;
while (!q.empty()) {
int q_size = q.size();
while (q_size--) {
int x = q.front().x;
int y = q.front().y;
int dir = q.front().dir;
int now_dist = dist[x][y][dir];
q.pop();
if ((x == N - 1 && y == N - 1) || (x + dx[dir] == N - 1 && y + dy[dir] == N - 1)) {
return dist[x][y][dir];
}
// 이동하는 경우
for (int k = 0; k < 4; k++) {
int nx1 = x + dx[k];
int ny1 = y + dy[k];
int nx2 = x + dx[dir] + dx[k];
int ny2 = y + dy[dir] + dy[k];
if (!is_range(nx1, ny1, board) || !is_range(nx2, ny2, board)) continue;
if (board[nx1][ny1] || board[nx2][ny2] || dist[nx1][ny1][dir] != -1) continue;
dist[nx1][ny1][dir] = now_dist + 1;
q.push({ nx1,ny1,dir });
}
// 첫번째 칸이 회전하는 경우
check(x, y, dir, 0, now_dist, board);
check(x, y, dir, 1, now_dist,board);
// 두번째 칸이 회전하는 경우
check(x + dx[dir], y + dy[dir], (dir + 2) % 4, 0,now_dist,board);
check(x + dx[dir], y + dy[dir], (dir + 2) % 4, 1,now_dist,board);
}
}
}
디버깅
현재 거리를 따로 변수로 지정해두지 않아서 이를 check함수에 적용하는데 애를 먹었습니다.
제출결과
마무리
회전하는 상태를 어떻게 표현하느냐가 관건인 완전탐색 문제였습니다.