[Java] Lv.2 리코쳇 로봇

문제

문제 설명
리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로,
시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서
게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....
여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 
7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 
말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 
만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한 사항
3 ≤ board의 길이 ≤ 100
3 ≤ board의 원소의 길이 ≤ 100
board의 원소의 길이는 모두 동일합니다.

문자열은 ".", "D", "R", "G"로만 구성되어 있으며
각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.

"R"과 "G"는 한 번씩 등장합니다.

프로그래머스

 

문제 풀이

아래 블로그 글을 참고하여 풀이 했다.

시작점을 찾아서 해당 위치부터 큐에 넣고 네 방향으로 D 혹은 맵의 맨끝에 도달할 때까지 확인한다.

장애물에 부딫히거나 맨끝에 도달할 경우 해당 위치를 다시 시작점으로 큐에 넣고 횟수를 +1 하는 방식으로 계속 진행한다.

G 지점에 도달했을 때 이전에 도달했었던 이동 횟수와 비교하여 더 작은 숫자를 다시 기록한다.

[프로그래머스] 리코쳇 로봇 - Java(자바)

 

자바 코드

import java.util.*;
class Solution {
    public int solution(String[] board) {
        int answer = Integer.MAX_VALUE;
        // 방문 처리를 위한 배열
        boolean[][] visit = new boolean[board.length][board[0].length()];
        
        // 현재 위치를 저장할 큐
        Queue<int[]> que = new LinkedList<>();
        
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length(); j++){
                // 시작점을 찾으면 해당 위치를 큐에 삽입하고 방문처리
                if(board[i].charAt(j) == 'R') {
                    que.add(new int[] {i, j, 0});
                    visit[i][j] = true;
                    
                    // 큐가 빌때까지 반복
                    while(!que.isEmpty()){
                        int[] tmp = que.poll();
                        
                        // 뽑은 현재 위치가 도착지점이면 현재의 답과 비교하여 작은 쪽을 저장
                        if(board[tmp[0]].charAt(tmp[1]) == 'G') {
                            answer = Math.min(answer, tmp[2]);
                        }
                        
                        // 네 방향으로 탐색
                        for(int k = 0; k < 4; k++){
                            // 상 하 좌 우, x, y, 이동 횟수, 보드게임판
                            // 상하좌우 값을 확인하여 한 방향을 확인하고 멈춘 위치를 반환한다.
                            int[] XY = move(k, tmp[0] , tmp[1], tmp[2], board);
                            int x = XY[0];
                            int y = XY[1];
                            
                            // 부딫힌 위치가 방문하지 않은 위치일 경우
                            // 해당 위치를 현재 위치로 저장하고 방문처리
                            if(!visit[x][y]){
                                que.add(XY);
                                visit[x][y] = true;
                            }
                        }
                    }
                }
            }
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    // 상하좌우 장애물이나 맨 끝에 부딪힐때까지 미끄러지기
    public int[] move(int k, int x, int y, int cnt, String[] board){
        int[] result = new int[3];
        
        // 상
        if(k == 0){
            // 현재 x위치부터 맨 위 0까지 확인
            for(int i = x; i >= 0; i--){
                // 현재 i줄의 y 좌표가 D, 즉 벽일 경우 해당 위치를 반환한다.
                if(board[i].charAt(y) == 'D'){
                    return new int[]{i + 1, y, cnt + 1};
                }
            }
            
            // 위의 반복문에 걸리지 않았을 경우 보드판 y열의 맨 위 끝에 붙은 것이다.
            result[0] = 0;
            result[1] = y;
            result[2] = cnt + 1;
        }else if(k == 1){ // 하
            // 현재 x위치부터 맨 아래 board.length -1 까지 확인
            for(int i = x; i < board.length; i++){
                // 현재 i줄의 y 좌표가 D, 즉 벽일 경우 해당 위치를 반환한다.
                if(board[i].charAt(y) == 'D'){
                    return new int[]{i - 1, y, cnt + 1};
                }
            }            
            
            // 위의 반복문에 걸리지 않았을 경우 보드판 y열의 맨 아래 끝에 붙은 것이다.
            result[0] = board.length - 1;
            result[1] = y;
            result[2] = cnt + 1;
        }else if(k == 2){ // 우
            // 현재 y위치부터 맨 오른쪽 board.length -1 까지 확인
            for(int i = y; i < board[0].length(); i++){
                // 현재 i줄의 x 좌표가 D, 즉 벽일 경우 해당 위치를 반환한다.
                if(board[x].charAt(i) == 'D'){
                    return new int[]{x, i - 1, cnt + 1};
                }
            }            
            
            // 위의 반복문에 걸리지 않았을 경우 보드판 x행의 맨 오른쪽 끝에 붙은 것이다.
            result[0] = x;
            result[1] = board[0].length() - 1;
            result[2] = cnt + 1;
        }else if(k == 3){
            // 현재 y위치부터 맨 왼쪽 0 까지 확인
            for(int i = y; i >= 0; i--){
                // 현재 i줄의 x 좌표가 D, 즉 벽일 경우 해당 위치를 반환한다.
                if(board[x].charAt(i) == 'D'){
                    return new int[]{x, i + 1, cnt + 1};
                }
            }            
            
            // 위의 반복문에 걸리지 않았을 경우 보드판 x행의 맨 왼쪽 끝에 붙은 것이다.
            result[0] = x;
            result[1] = 0;
            result[2] = cnt + 1;
        }
        
        // 장애물에 걸리지 않고 벽에 부딫힌 위치를 반환
        return result;
    }
}