리코쳇 로봇

문제 설명

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

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 출발한 뒤 목표 위치에 정확하게 멈추기 위해 최소 몇 번의 이동이 필요한지 말하는 게임입니다.

이 게임에서 말의 이동은 현재 위치에서 상, 하, 좌, 우 중 한 방향으로 게임판 위의 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.

다음은 보드게임판을 나타낸 예시입니다. ("."은 빈 공간을, "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"는 한 번씩 등장합니다.

입출력 예

아이디어

최단거리 문제고 bfs로 해결가능한 문제다
로봇이 한번 움직일 때 끝까지(벽에 부딪힐 때까지 = 벽의 직전 위치까지) 움직이기 때문에 중간에 while문이 한번 더 들어간다
순회 여부를 체크하는 배열로 체크하면서 나간다

JAVA 풀이

import java.util.*;

class Point{
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Solution {
    public int solution(String[] board) {
        int answer = -1;
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int[][] visited = new int[board.length][board[0].length()];
        Queue<Point> q = new LinkedList();
        for (int i = 0 ; i < board.length; i++) {
            for (int j = 0 ; j < board[0].length(); j++) {
                if (board[i].charAt(j) == 'R') {
                    q.add(new Point(i, j));
                    visited[i][j] = 1;
                    break;
                }
            }
        }

        while (!q.isEmpty()) {
            Point p = q.poll();
            if (board[p.x].charAt(p.y) == 'G') {
                answer = visited[p.x][p.y] - 1;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                while (true) {
                    if (0 <= nx 
                        && nx < board.length 
                        && 0 <= ny 
                        && ny < board[0].length()
                        && board[nx].charAt(ny) != 'D') {

                        nx += dx[i];
                        ny += dy[i];
                    } else {
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                }

                if (visited[nx][ny] == 0) {
                    q.add(new Point(nx, ny));
                    visited[nx][ny] = visited[p.x][p.y] + 1;
                }
            }
        }
        return answer;
    }
}