[리코쳇 로봇] 코딩테스트 연습 > 연습문제 > 리코쳇 로봇
※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]
리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 출발한 뒤 목표 위치에 정확하게 멈추기 위해 최소 몇 번의 이동이 필요한지 말하는 게임입니다.
이 게임에서 말의 이동은 현재 위치에서 상, 하, 좌, 우 중 한 방향으로 게임판 위의 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.
다음은 보드게임판을 나타낸 예시입니다. ("."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.)
...D..R
.D.G...
....D.D
D....D.
..D....
이때 최소 움직임은 7번이며 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 "G" 위치에 멈춰 설 수 있습니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성해주세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.
제한 사항
- 3 ≤ board의 길이 ≤ 100
- 3 ≤ board의 원소의 길이 ≤ 100
- board의 원소의 길이는 모두 동일합니다.
- 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
- "R"과 "G"는 한 번씩 등장합니다.
입출력 예
입출력 예 설명
입출력 예 #1
- 문제 설명의 예시와 같습니다.
입출력 예 #2
.D.R
....
.G..
...D
- "R" 위치에 있는 말을 어떻게 움직여도 "G" 에 도달시킬 수 없습니다.
- 따라서 -1을 return 합니다.
[간단설명]
리코쳇 Rule을 이용해서 시작점에서 종료점까지 최소 이동횟수 구하기
** 리코쳇 로봇이해하기
ㄴ 한번 이동시에 1칸씩 움직이는게 아니라, 장애물 or 벽을 만났때까지 이동한다.
[접근방법]
1. 시작점, 종료점을 찾는다.
2. 최소값을 지정한다.
3. 큐를 사용해서 BFS 탐색을 구현한다.(최단거리)
4. 위, 아래, 왼쪽, 오른쪽 전부 탐색한다.
5. 방문한 좌표는 탐색하지 않는다.
6. 최소값이 바뀌지 않았으면 -1을 리턴한다.(종료점에 도달하지 못했으면)
7. 이동횟수 최소값을 리턴한다.
[주의사항]
- 방문체크를 하지 않으면, 효율성에서 탈락한다.
- 종료점에 도달하지 못하는 경우는 -1을 리턴해야한다.(여기에서는 최소값으로 구분)
- 귀찮아서 통과할 정도로만 소스를 구현했는데, 다른 간결한 방법도 찾아보자
[소스공개]
import java.util.*;
class Solution {
public int solution(String[] board) {
// 시작점, 종료점 배열
int[] start = new int[2];
int[] end = new int[2];
// 시작점, 종료점 찾기
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length();j++){
if('R'==board[i].charAt(j)){
start=new int[]{i,j,0,0};
}else if('G'==board[i].charAt(j)){
end=new int[]{i,j,0,0};
}
}
}
// 방문기록
boolean[][] visited = new boolean[board.length][board[0].length()];
// BFS용 queue
Queue<int[]> que = new LinkedList<>();
// 시작점을 큐에 넣는다.
que.offer(start);
int min = 10000; // board 길이 100 x 원소길이 100 = 10,000
// BFS 탐색
while(!que.isEmpty()){
// 현재 que 가져오기
int[] now = que.poll();
// 종료점에 도착했으면, 최소값 업데이트
if(now[0] == end[0] && now[1] == end[1]){
min=Math.min(now[3],min);
break;
}
// 방문했으면 PASS
if(visited[now[0]][now[1]]) continue;
// 방문체크
visited[now[0]][now[1]]= true;
// 위로 이동
// 이동할 수 있을때만, 큐에 넣는다.
int[] up = move(board,now,"up",now[3]);
if(up[2]==0){
que.offer(up);
}
// 아래로 이동
int[] down = move(board,now,"down",now[3]);
if(down[2]==0){
que.offer(down);
}
// 왼쪽 이동
int[] left = move(board,now,"left",now[3]);
if(left[2]==0){
que.offer(left);
}
// 오른쪽 이동
int[] right = move(board,now,"right",now[3]);
if(right[2]==0){
que.offer(right);
}
}
// 종료점에 도달하지 못하면 -1 리턴
if(min==10000) return -1;
// 최소값 리턴
return min;
}
private int[] move(String[] board,int[] now, String direction, int sum){
int y=now[0]; // y좌표
int x=now[1]; // x좌표
// 명령어가 up이면
if("up".equals(direction)){
// 경계를 벗어나면, -1리턴
if(y-1 < 0) {
return new int[]{y,x,-1,sum};
}
// 범위에 있으면, sum+1 리턴
else{
int cnt=0;
for(int i=y-1;i>=0;i--){
if('D'==board[i].charAt(x)){
break;
}else{
cnt++;
}
}
return new int[]{y-cnt,x,0,sum+1};
}
// 명령어가 down이면
}else if("down".equals(direction)){
if(y+1 > board.length-1) {
return new int[]{y,x,-1,sum};
}
else{
int cnt=0;
for(int i=y+1;i<board.length;i++){
if('D'==board[i].charAt(x)){
break;
}else{
cnt++;
}
}
return new int[]{y+cnt,x,0,sum+1};
}
// 명령어가 left이면
}else if("left".equals(direction)){
if(x-1 < 0) {
return new int[]{y,x,-1,sum};
}
else{
int cnt=0;
for(int i=x-1;i>=0;i--){
if('D'==board[y].charAt(i)){
break;
}else{
cnt++;
}
}
return new int[]{y,x-cnt,0,sum+1};
}
// 명령어가 right이면
}else if("right".equals(direction)){
if(x+1 > board[0].length()-1) {
return new int[]{y,x,-1,sum};
}
else{
int cnt=0;
for(int i=x+1;i<board[0].length();i++){
if('D'==board[y].charAt(i)){
break;
}else{
cnt++;
}
}
return new int[]{y,x+cnt,0,sum+1};
}
}
return new int[]{0,0,0,0};
}
}
[실행결과]
