[프로그래머스] 리코쳇 로봇

문제 링크

프로그래머스

문제 설명

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

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

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

입출력 예

board	result
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]	7
[".D.R", "....", ".G..", "...D"]	-1

 

문제 풀이

[고려사항]

시작 위치부터 목표 위치까지 모든 경로 중 최소 움직임을 찾아야한다. 

board의 최대 크기는 100 * 100(10,000)이므로, 모든 가능한 경로를 탐색하는 방식으로 구현한다면 시간을 초과한다.

그래서 최단 거리를 찾는 알고리즘으로 BFS를 이용해서 구현한다.

BFS로 구현할 경우에는, 모든 노드를 4방향으로 방문하기 때문에 최악의 경우라도, O(10,000)이 된다.

[알고리즘, 구현방법]

최단 경로를 찾는 문제이므로 BFS를 이용해서 구현했다.

여기서 말의 움직임은 장애물(D)이나 보드의 맨 끝에 부딪힐 때까지 미끄러지는 것이다. 

일반적인 BFS와 다른점은 이동하는 칸의 개수가 한 칸이 아니라, 장애물이나 벽에 부딪힐 때까지 최대한 갈 수 있는 n칸을 이동한다는 것이다.

즉, 상하좌우의 방향 중 한 칸만 움직이는것이 아니라 특정 방향으로 최대한 갈 수 있는 칸을 구해야한다.

그래서 BFS 방문 배열을 boolean이 아니라 int 로 선언해서 해당 지점까지의 이동 횟수를 저장했다.

[풀이 과정]

*자세한건 코드내에 주석을 확인하면서 따라가주세요!

1. 시작 위치 찾기(R)

2. 시작 위치를 Queue에 저장하고 BFS 수행

• 4방향에 대해 BFS 수행
• 한 방향에 대해 최대한 갈 수 있는 만큼 이동
• 벽이나 장애물에 부딪힌 경우, 벽이나 장애물을 부딪히기 전 좌표로 돌아와서, 해당 지점까지의 이동 횟수 저장하고 Queue에 저장하여 해당 지점부터 탐색
• 현재 지점이 목표 위치(G)라면 이동 횟수 answer에 저장하고 Break;

정답 코드

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

public class Solution {
    public int solution(String[] board) {
        int row = board.length;
        int col = board[0].length();
        int[][] cnt = new int[row][col];

        // 1. 시작 위치(R) 찾기
        Queue<Point> q = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i].charAt(j) == 'R') {
                    q.add(new Point(i, j));
                    cnt[i][j] = 1;
                    break;
                }
            }
        }

        // 2. BFS 탐색
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int answer = -1; // 목표위치에 도달할 수 없다면 -1을 return
        while (!q.isEmpty()) {
            Point current = q.poll();
            // 현재 지점이 목표 위치인지
            if (board[current.x].charAt(current.y) == 'G') {
                answer = cnt[current.x][current.y] - 1; // 시작 위치를 1로 초기화 했으므로, 이동 횟수는 -1
                break;
            }
            // 4방향에 대해 BFS를 수행
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                // 해당 방향으로 최대한 이동
                while (true) {
                    if ((nx >= 0 && nx < row && ny >= 0 && ny < col) && board[nx].charAt(ny) != 'D') {
                        nx += dx[i];
                        ny += dy[i];
                    } else { // 벽이나 장애물에 부딪힌 경우
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                }
                // 최대한 움직인 지점을 방문한 적이 없으면, 해당 지점에서 탐색
                if (cnt[nx][ny] == 0) {
                    q.add(new Point(nx, ny));
                    cnt[nx][ny] = cnt[current.x][current.y] + 1; // 현재 탐색을 시작한 위치에서 이동 횟수 +1
                }
            }
        }
        return answer;
    }

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