문제

https://school.programmers.co.kr/learn/courses/30/lessons/169199

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

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

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

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

...D..R
.D.G...
....D.D
D....D.
..D....

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

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

---

입력

String배열로 표현된 격자모양의 입력

---

출력

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

---

풀이

제한조건

3 ≤ board의 길이 ≤ 100
3 ≤ board의 원소의 길이 ≤ 100
board의 원소의 길이는 모두 동일합니다.
문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
"R"과 "G"는 한 번씩 등장합니다.

접근방법

전형적인 BFS를 통한 탐색이다.

문제만의 특이점이라고 한다면 2가지가 있다.

1. 출발점의 좌표를 직접 찾아야 한다.
2. 상하좌우의 방향 중 `한칸`을 이동하는것이 아니라, 특정 방향으로 갈 수 있는 `최대 칸`을 이동한다.

그리고 문제에서 목표 위치에 도착했을때, 최소 이동횟수를 구하는 것이므로, 특정 좌표를 방문했다 라는 정보를 표시할 때 Boolean 배열이 아닌 Int배열로 바로 depth를 표기하는 방식으로 진행한다.
( while문을 2개 사용해서 depth를 관리할 수도 있다.)

int depth = 0;
while(!q.isEmpty()){
	int size = q.size();
    while(size-- > 0){
    	// do something
    }
    depth++;
}

코드의 주석을 따라가보자.

---

코드

import java.util.*;

class Point{
    int x;
    int y;
    Point(int a, int b){
        x = a;
        y = b;
    }
}

class Solution {
    int N,M;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        int[][] visit = new int[N][M];
        Queue<Point> q = new ArrayDeque();
        
        // 우선 출발점의 좌표를 찾는다.
        for(int i = 0 ; i < N; ++i){
            String s = board[i];
            for(int j = 0 ; j < M; ++j){
                if(s.charAt(j) == 'R'){
                    q.add(new Point(i,j));
                    visit[i][j] = 1;
                    break;
                }
            }
        }
        
        // 도착지점에 도달하지 못한다면 -1을 반환.
        int answer = -1;
        while(!q.isEmpty()){
            Point cur = q.poll();
            // 현재 지점이 도착지점인가?
            if(board[cur.x].charAt(cur.y) == 'G'){
                answer = visit[cur.x][cur.y] - 1;
                break;
            }
            
            // 4가지 방향으로 탐색해본다.
            for(int d = 0 ; d < 4; ++d){
                int nextX = cur.x + dx[d];
                int nextY = cur.y + dy[d];
                while(true){ // 해당 방향으로 최대한 끝까지 이동해본다.
                    if(isInRange(nextX, nextY) && board[nextX].charAt(nextY) != 'D'){
                        nextX += dx[d];
                        nextY += dy[d];
                    }else{
                    	// 현재 지점은 보드 밖이거나, 장애물이 있는 지점이다. 직전의 좌표가 이동할 수 있는 좌표이다.
                        nextX -= dx[d];
                        nextY -= dy[d];
                        break;
                    }
                }
                
                // 해당 지점에 방문한적이 없다면, 해당 지점에서 탐색한다.
                if(visit[nextX][nextY] == 0){
                    q.add(new Point(nextX, nextY));
                    visit[nextX][nextY] = visit[cur.x][cur.y] + 1;
                }
            }
        }
        
        return answer;
    }
    
    public boolean isInRange(int x, int y){
        if(0 <= x && x < N && 0 <= y && y < M)
            return true;
        return false;
    }
}