문제
로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
입출력 예에 대한 설명
문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.
구현코드
import java.util.*;
class Node{
private int x1; // 첫번째 좌표
private int y1;
private int x2; // 두번째 좌표
private int y2;
private int dis; // 이동거리
public Node(int x1, int y1, int x2, int y2, int dis){
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.dis = dis;
}
public int getX1(){
return this.x1;
}
public int getY1(){
return this.y1;
}
public int getX2(){
return this.x2;
}
public int getY2(){
return this.y2;
}
public int getDis(){
return this.dis;
}
}
class Solution {
public static int[][] newBoard;
public int solution(int[][] board) {
// 기존에 있던 board 겉면을 모드 벽으로 둘러싸기 범위체크 수월하게 하기위해
int n = board.length;
newBoard = new int[n+2][n+2];
for(int i = 0; i < n+2; i++){
for(int j = 0; j < n+2; j++){
newBoard[i][j] = 1;
}
}
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j++){
newBoard[i+1][j+1] = board[i][j];
}
}
//넓이우선탐색 BFS 실행
Queue<Node>q = new LinkedList<>();
ArrayList<Node>visited = new ArrayList<>(); // 방문여부를 구해야 하는데 가로로 있을 때와 세로로 있을때를 구분해주어야한다.
// 그래서 ArrayList 를 사용해서 좌표값으로 비교.
q.offer(new Node(1 ,1 ,1 ,2, 0)); // 시작점 queue 에 추가.
visited.add(new Node(1 ,1 ,1 ,2, 0)); // 방문여부에도 추가.
// 큐가 빌 때까지 반복
while(!q.isEmpty()){
Node now = q.poll();
// (n , n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
if ((now.getX1() == n && now.getY1() == n) || (now.getX2() == n && now.getY2() == n)) {
return now.getDis();
}
// 현재 위치에서 이동할 수 있는 위치 확인
ArrayList<Node> move = possibleMove(now, newBoard);// 상하좌우, 회전이 가능한지 판단한 ArrayList를 return 받는다.
for(Node pos : move){
// 방문여부 체크 변수 방문하지 않았다면 queue 에 추가
boolean check = true;
for(Node visit: visited){
if(pos.getX1() == visit.getX1() && pos.getY1() == visit.getY1() && pos.getX2() == visit.getX2() && pos.getY2() == visit.getY2() ){
check = false;
break;
}
}
if(check){
q.offer(pos);
visited.add(pos);
}
}
}
return 0;
}
public ArrayList<Node>possibleMove(Node now, int[][] newBoard){
ArrayList<Node> move = new ArrayList<>();
int[] dx = {-1, 1, 0 ,0};
int[] dy = {0, 0, -1, 1};
// 상하좌우 확인 후 가능하다면 ArrayList 에 add
for(int i = 0; i < 4; i++){
int nx1 = now.getX1() + dx[i];
int ny1 = now.getY1() + dy[i];
int nx2 = now.getX2() + dx[i];
int ny2 = now.getY2() + dy[i];
int ndis = now.getDis() +1;
if(newBoard[nx1][ny1] == 0 && newBoard[nx2][ny2] == 0){
move.add(new Node(nx1 ,ny1 ,nx2, ny2, ndis));
}
}
int[] dk = {-1 ,1};
// 방향이 세로일 때
if(now.getY1() == now.getY2()){
// 왼쪽으로 회전할지 오른쪽으로 회전할지 판단.
for(int i = 0 ; i < 2; i++){
if(newBoard[now.getX1()][now.getY1() + dk[i]] == 0 && newBoard[now.getX2()][now.getY2() + dk[i]] == 0){
move.add(new Node(now.getX1(), now.getY1(), now.getX1(), now.getY1() + dk[i], now.getDis() + 1 ));
move.add(new Node(now.getX2(), now.getY2(), now.getX2(), now.getY2() + dk[i], now.getDis() + 1 ));
}
}
}
// 방향이 가로일 때
if(now.getX1() == now.getX2()){
// 위쪽으로 회전할지 아래쪽으로 회전할지 판단.
for(int i = 0 ; i < 2; i++){
if(newBoard[now.getX1() + dk[i]][now.getY1()] == 0 && newBoard[now.getX2() + dk[i]][now.getY2()] == 0){
move.add(new Node(now.getX1(), now.getY1(), now.getX1() + dk[i], now.getY1() , now.getDis() + 1 ));
move.add(new Node(now.getX2(), now.getY2(), now.getX2() + dk[i], now.getY2() , now.getDis() + 1 ));
}
}
}
return move;
}
}코드해석
이 문제는 미로찾기 문제와 비슷하지만, 두칸을 차지하고있고 회전가능한 것이 다른 문제이다. 우리는 미로찾기를 할때 방문여부를 확인하여 최단경로를 알아낼 수있었다. 하지만 두칸을 차지하고있고, 회전까지 가능한 로봇의 방문여부를 어떻게확인할 수있을까? 다른 분들의 풀이를 보면 3차원배열을 이용하여 방문여부를 비교하였지만 나는 ArrayList를 사용하여 좌표값들을 넣어주고, 비교하고자 하는 값을 매번 비교해주는 방법을 선택하였다.
또한 이문제는 상하좌우만 비교하면 되는 문제들과 달리 , 상하좌우, 회전 까지 확인해야하기 때문에 움직일수있는 값들을 ArrayList 에 담아서 return 하는 메서드를 구현하여 사용하였다. 상하좌우는 간단하기 때문에 패스하고, 회전은 가로일때 회전방법, 세로일때 회전방법이 다르다. 가로일때와 세로일 때의 값 비교법은 y좌표 값이 같다면 세로, x좌표값이 같다면 가로로 판단하였다. 또한 화전을 하기 위해선 화전하려고하는 방향의 값들이 0이어야 한다. 그래서 0인것을 판단하루 0이라면
ArrayList에 두가지 회전을 담는 방식을 사용하였다. 어려운 문제임으로 다시보면 좋은문제인거같다.
