[프로그래머스 Level.3] 블록 이동하기 (2020 KAKAO BLIND RECRUITMENT) (Java)
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60063
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 블록 이동하기
문제 설명
로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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초가 걸립니다.
나의 코드
import java.util.*;
class Solution {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int[][] board;
boolean[][][] visited;
public int solution(int[][] board) {
int answer = 0;
this.board = board;
visited = new boolean[board.length][board.length][2]; // 0 -> 수평, 1 -> 수직
answer = bfs(0, 0, 0, 1);
return answer;
}
public int bfs(int x1, int y1, int x2, int y2) {
Queue<Robot> q = new LinkedList<>();
q.offer(new Robot(x1, y1, x2, y2, 0, 0));
while(!q.isEmpty()) {
Robot robot = q.poll();
if((robot.x1 == board.length - 1 && robot.y1 == board.length - 1)
|| (robot.x2 == board.length - 1 && robot.y2 == board.length - 1))
return robot.cost;
if(visited[robot.x1][robot.y1][robot.status] && visited[robot.x2][robot.y2][robot.status]) continue;
visited[robot.x1][robot.y1][robot.status] = true;
visited[robot.x2][robot.y2][robot.status] = true;
for(int i=0; i<4; i++) {
int nx1 = robot.x1 + dy[i];
int ny1 = robot.y1 + dx[i];
int nx2 = robot.x2 + dy[i];
int ny2 = robot.y2 + dx[i];
if(nx1 < 0 || ny1 < 0 || nx1 >= board.length || ny1 >= board.length
|| nx2 < 0 || ny2 < 0 || nx2 >= board.length || ny2 >= board.length) continue;
if(board[nx1][ny1] == 1 || board[nx2][ny2] == 1) continue;
if(visited[nx1][ny1][robot.status] && visited[nx2][ny2][robot.status]) continue;
q.offer(new Robot(nx1, ny1, nx2, ny2, robot.cost + 1, robot.status));
}
// 수평 -> 수직 회전
if(robot.status == 0) {
if(robot.x1 - 1 >= 0 && board[robot.x1 - 1][robot.y1] == 0 && board[robot.x2 - 1][robot.y2] == 0) {
q.offer(new Robot(robot.x1, robot.y1, robot.x1 - 1, robot.y1, robot.cost + 1, 1));
q.offer(new Robot(robot.x2 - 1, robot.y2, robot.x2, robot.y2, robot.cost + 1, 1));
}
if(robot.x1 + 1 < board.length && board[robot.x1 + 1][robot.y1] == 0 && board[robot.x2 + 1][robot.y2] == 0) {
q.offer(new Robot(robot.x1, robot.y1, robot.x1 + 1, robot.y1, robot.cost + 1, 1));
q.offer(new Robot(robot.x2 + 1, robot.y2, robot.x2, robot.y2, robot.cost + 1, 1));
}
}
// 수직 -> 수평 회전
if(robot.status == 1) {
if(robot.y1 - 1 >= 0 && board[robot.x1][robot.y1 - 1] == 0 && board[robot.x2][robot.y2 - 1] == 0) {
q.offer(new Robot(robot.x1, robot.y1 - 1, robot.x1, robot.y1, robot.cost + 1, 0));
q.offer(new Robot(robot.x2, robot.y2 - 1, robot.x2, robot.y2, robot.cost + 1, 0));
}
if(robot.y1 + 1 < board.length && board[robot.x1][robot.y1 + 1] == 0 && board[robot.x2][robot.y2 + 1] == 0) {
q.offer(new Robot(robot.x1, robot.y1, robot.x1, robot.y1 + 1, robot.cost + 1, 0));
q.offer(new Robot(robot.x2, robot.y2, robot.x2, robot.y2 + 1, robot.cost + 1, 0));
}
}
}
return -1;
}
class Robot {
int x1;
int y1;
int x2;
int y2;
int cost;
int status;
public Robot(int x1, int y1, int x2, int y2, int cost, int status) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.cost = cost;
this.status = status;
}
}
}
풀이
- 출발점에서 막힌 벽을 피해서 도착점까지의 최단거리를 구하는 문제로 bfs를 이용하여 풀면 되는데 로봇이 좌표를 2개씩 사용하므로 좌표를 2개씩 세트로 움직이도록 만들면 된다. 또한, 로봇이 회전이 가능하므로 bfs를 진행할 때마다 회전이 가능하다면 수평->수직, 수직->수평 회전을 시켜주는 것도 포함시켜주어야 한다. 따라서 방문한 좌표의 체크를 체크할 때 수평 상태일 때 방문한 것과 수직 상태일 때 방문한 것을 따로 체크해주어야 하므로 visited를 3차원 배열로 생성하여 로봇의 수직, 수평 상태에 따라 방문한 좌표를 관리한다.
- 로봇이 위치한 2칸의 좌표(x1, y1, x2, y2)와 수직 또는 수평의 상태(status), 이동한 시간(cost)을 멤버 변수로 갖는 Robot 클래스를 생성한다.
- 3차원 배열 visited를 생성하고 로봇의 스타트 지점인 (0, 0), (0, 1)에서 도착점(board.length -1, board.length -1)까지 완전탐색 bfs를 진행한다.
- Robot 객체를 선언타입으로 하는 Queue를 생성하고 첫 출발 상태의 로봇의 좌표(0, 0, 0, 1)와 상태(수평), 이동한 시간(0)을 갖는 Robot을 생성하여 담는다.
- 이제 Queue가 빌 때까지 반복하는 while문을 생성하고 Queue의 첫 데이터를 꺼내어 해당 로봇의 좌표가 도착점(board.length -1, board.length -1)을 포함한다면 해당 로봇의 이동한 시간(robot.cost)을 반환하고 아니라면 해당 로봇의 상태(status)에 따른 두 좌표(x1, y1) (x2, y2)의 visited를 true로 변경하여 방문한 좌표를 체크하고 로봇을 상하좌우로 한 칸씩 이동한 좌표가 board의 좌표 범위를 벗어나지 않고 board의 값이 1이 아니고 방문하지 않았다면 이동한 좌표와 상태에다가 이동한 시간을 1 추가시켜 Robot을 생성하고 Queue에 담는다.
- 이제 여기다가 로봇이 회전하는 경우도 Queue에 담아주어 완전탐색을 해야하므로 로봇의 상태(status)가 수평(0)이라면 로봇의 윗 좌표가 존재하고(robot.x1 >= 1) 윗 좌표가 둘 다 벽이 아니라면 회전이 가능하므로 왼쪽 좌표를 기준으로 위쪽으로 회전한 경우와 오른쪽 좌표를 기준으로 위쪽으로 회전한 경우를 Queue에 담아주고 마찬가지로 로봇의 아랫 좌표가 존재하고(robot.x1 + 1 < board.length) 아랫 좌표가 둘 다 벽이 아니라면 왼쪽 좌표를 기준으로 아래쪽으로 회전한 경우와 오른쪽 좌표를 기준으로 아래쪽으로 회전한 경우를 Queue에 담아준다.
- 또한, 로봇의 상태(status)가 수직(1)이라면 로봇의 왼쪽 좌표가 존재하고(robot.y1 >= 1) 왼쪽 좌표가 둘 다 벽이 아니라면 회전이 가능하므로 위쪽 좌표를 기준으로 왼쪽으로 회전한 경우와 아랫쪽 좌표를 기준으로 왼쪽으로 회전한 경우를 Queue에 담아주고 마찬가지로 로봇의 오른쪽 좌표가 존재하고( robot.y1 + 1 < board.length) 둘 다 벽이 아니라면 위쪽 좌표를 기준으로 오른쪽으로 회전한 경우와 아래쪽 좌표를 기준으로 오른쪽으로 회전한 경우를 Queue에 담아준다.
- 이렇게 로봇이 상하좌우로 이동한 경우와 회전한 경우를 모두 Queue에 담아가며 제일 먼저 도착점에 도달한 Robot의 cost를 answer에 저장하고 answer를 반환한다.