링크

문제링크

문제

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

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

이 게임에서 말의 움직임은 상, 하, 좌, 우 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"는 한 번씩 등장합니다.

입출력

begin	return
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]	7
[".D.R", "....", ".G..", "...D"]	-1

해결

다른 퍼즐게임들에서 빙판위에서 움직이는 것 처럼 로봇이 D를 만나거나 빙판 모서리까지 움직이면 멈출수있고 이러한 움직임으로 G까지 도달하는 게임이다.

최소한의 움직임으로 G까지 도달하고싶기에 BFS를 사용하여 탐색한다.

distMaps는board에서 각 위치까지 도달하는대 최소한의 움직임 횟수를 저장한다.

bfs()에서 posQueue는 {행 인덱스, 열 인덱스, 이동 횟수}를 담고 있다.
posQueue가 다 빌때까지
다음 이동 할 좌표와 깊이를 posQueue에서 받고
그 지점의 현재 이동횟수를 distMaps 로 확인하고 curDepth와 비교하여 적은값을 distMaps에 기록한다.
board에 현재 위치를 V로 표기해 방문한곳으로 표시한다.

현재위치에서 다음으로 이동할 수 있는 곳을 탐색한다.
상, 하, 좌, 우를 D를 만나거나 가장자리까지 움직일때까지 탐색하고 그 위치가 방문한 곳이 아니라면
posQueue에 추가한다.

bfs()가 종료되었다면 distMaps위 G위치를 확인하여 최소 이동거리를 얻는다.

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(String[] board) {
        int answer = 0;
        
        int row = 0;
        int col = 0;
        int goalRow = 0;
        int goalCol = 0;

        int[][] distMaps = new int[board.length][board[0].length()];

        //초기 위치 탐색
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length(); j++) {
                if (board[i].charAt(j) == 'R') {
                    row = i;
                    col = j;
                }
                if (board[i].charAt(j) == 'G') {
                    goalRow = i;
                    goalCol = j;
                }
            }
        }

        bfs(board, distMaps, row, col, 0);
        answer = distMaps[goalRow][goalCol];
        
        if (answer == 0) answer = -1;
        
        return answer;
    }
    
    private static int bfs(String[] board, int[][] distMaps, int row, int col, int depth) {

        Queue<int[]> posQueue = new LinkedList<>();
        posQueue.add(new int[]{row, col, depth});

        while (!posQueue.isEmpty()) {

            int[] nextPos = posQueue.poll();
            int nextRow = nextPos[0];
            int nextCol = nextPos[1];
            int curDepth = nextPos[2];

            distMaps[nextRow][nextCol] = distMaps[nextRow][nextCol] > 0 ? Math.min(distMaps[nextRow][nextCol], curDepth) : curDepth;

            //도착한 곳은 V로 표시
            StringBuilder sb = new StringBuilder(board[nextRow]);
            sb.replace(nextCol, nextCol + 1, "V");
            board[nextRow] = sb.toString();

            int right = 0;
            int left = 0;
            int up = 0;
            int down = 0;

            //상, 하, 좌, 우 좌표찾기
            for (int i = nextCol; i < board[nextRow].length(); i++) {
                if (i == board[nextRow].length() - 1 || board[nextRow].charAt(i + 1) == 'D') {
                    right = i;
                    if (right != nextCol && board[nextRow].charAt(i) != 'V') {
                        posQueue.add(new int[]{nextRow, right, curDepth + 1});
                    }
                    break;
                }
            }

            for (int i = nextCol; i >= 0; i--) {
                if (i == 0 || board[nextRow].charAt(i - 1) == 'D') {
                    left = i;
                    if (left != nextCol && board[nextRow].charAt(i) != 'V') {
                        posQueue.add(new int[]{nextRow, left, curDepth + 1});
                    }
                    break;
                }
            }

            for (int i = nextRow; i >= 0; i--) {
                if (i == 0 || board[i - 1].charAt(nextCol) == 'D') {
                    up = i;
                    if (up != nextRow && board[i].charAt(nextCol) != 'V') {
                        posQueue.add(new int[]{up, nextCol, curDepth + 1});
                    }
                    break;
                }
            }

            for (int i = nextRow; i < board.length; i++) {
                if (i == board.length - 1 || board[i + 1].charAt(nextCol) == 'D') {
                    down = i;
                    if (down != nextRow && board[i].charAt(nextCol) != 'V') {
                        posQueue.add(new int[]{down, nextCol, curDepth + 1});
                    }
                    break;
                }
            }
        }

        return 0;
    }
}