[프로그래머스] 블록 이동하기
문제 설명
로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
입출력 예
board / result
| [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] | 7 |
입출력 예에 대한 설명
문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다.
다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다.
이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다.
따라서 목적지에 도달하기까지 최소 7초가 걸립니다.
풀이
- BFS 사용
- 블록이 이동할 수 있는 케이스를 검사해서 이동 가능하면 queue에 넣어주기
: 상,하,좌,우, 가로회전, 세로회전
: 가로 회전 - 해당 블록 위or 아래가 다 비어있어야 회전가능
: 세로 회전 - 해당 블록 좌or우가 다 비어있어야 회전 가능
- 방문체크해서 방문하지 않은 것만 넣어주기
- 각 방문Node에 여태까지의 dist값을 넣어주어 N에 도달했을 때 해당 값 리턴
*방문 체크하는 법
1) 4차원 배열 사용 - 느림
2) hashCode, equals 함수 오버라이딩해서 사용
- equals 함수를 오버라이딩 하면 객체 간의 비교에서 객체 내부 변수들로 비교가 가능하다고 한다.
- 하지만 equals 함수만 오버라이딩 하면 hashCode로 비교하는 hashMap, hashSet에선 다른 객체로 나옴.
- 따라서 hashCode()도 같이 오버라이딩 해주기!
import java.util.*;
class Node{
int x;
int y;
int x2;
int y2;
int dist;
Node(int x, int y, int x2, int y2, int dist){
this.x = x;
this.y = y;
this.x2 = x2;
this.y2 = y2;
this.dist = dist;
}
@Override
public int hashCode(){
int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
result = prime * result + x2;
result = prime * result + y2;
return result;
}
@Override
public boolean equals(Object obj){
Node node = (Node)obj;
if(this.x == node.x && this.y == node.y && this.x2 == node.x2 && this.y2 == node.y2) return true;
if(this.x == node.x2 && this.y == node.y2 && this.x2 == node.x && this.y2 == node.y) return true;
return false;
}
}
class Solution {
int N;
int[][] nboard;
HashSet<Node> check = new HashSet<>();
Queue<Node> q = new LinkedList<>();
int answer = 0;
public int solution(int[][] board) {
N = board.length;
nboard = new int[N+2][N+2];
//패딩 만들어주기
for(int i=0; i<N+2; i++){
for(int j=0; j<N+2; j++){
if(i==0 || j==0 || i==N+1 || j==N+1){
nboard[i][j] = 1;
continue;
}
nboard[i][j] = board[i-1][j-1];
}
}
push(1,1,1,2,0);
bfs();
return answer;
}
public void bfs(){
int[][] dir ={{-1,0},{1,0},{0,-1},{0,1}};
int[] rotate = {-1,1};
while(!q.isEmpty()){
Node n = q.poll();
int d = n.dist;
//도착
if((n.x == N && n.y == N) || (n.x2 == N && n.y2 == N)){
answer = d - 1;
break;
}
//상하좌우 이동 체크
for(int i=0; i<4; i++){
int nx = n.x + dir[i][0];
int ny = n.y + dir[i][1];
int nx2 = n.x2 + dir[i][0];
int ny2 = n.y2 + dir[i][1];
if(nboard[nx][ny] == 0 && nboard[nx2][ny2] == 0){
push(nx, ny, nx2, ny2, d);
}
}
//가로->세로 회전 체크
if(n.x == n.x2){
for(int i=0; i<2; i++){
int nx = n.x + rotate[i];
int ny = n.y;
int nx2 = n.x2 + rotate[i];
int ny2 = n.y2;
if(nboard[nx][ny] == 0 && nboard[nx2][ny2] == 0){
push(n.x, n.y, nx, ny, d);
push(n.x2, n.y2, nx2, ny2, d);
}
}
}
//세로->가로 회전 체크
else{
for(int i=0; i<2; i++){
int nx = n.x;
int ny = n.y + rotate[i];
int nx2 = n.x2;
int ny2 = n.y2 + rotate[i];
if(nboard[nx][ny] == 0 && nboard[nx2][ny2] == 0){
push(n.x, n.y, nx, ny, d);
push(n.x2, n.y2, nx2, ny2, d);
}
}
}
}
}
public void push(int x, int y, int x2, int y2, int dist){
Node n = new Node(x, y, x2, y2, dist+1);
if(check.contains(n)) return;
check.add(n);
q.offer(n);
}
}
셀프 피드백
- bfs 이해도 더 높이기
- hashCode, equals 오버라이딩 처음 알았음
- A* 공부하기!