[프로그래머스] LV2 리코쳇 로봇 (JAVA)

문제

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

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

 

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

 

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

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

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

 

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

 

문제풀이

import java.util.*;
class Solution {
    int[] start;
    boolean[][] visited;
    char[][] map;
    int[] dx = {0,-1,0,1};
    int[] dy = {1,0,-1,0};
    public int solution(String[] board) {
        //상, 하, 좌, 우 하나를 선택해 게임판 위 장애물이나 끝에 부딪힐 때 미끄러져 이동하는 것을 1번
        visited = new boolean[board.length][board[0].length()];
        map = new char[board.length][board[0].length()];
        
        //맵 완성...!하면서 R의 위치를 찾아보자
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length(); j++) {
                char tmp = board[i].charAt(j);
                if(tmp == 'R') {
                    start = new int[] {i, j};
                }
                map[i][j] = tmp;
            }
        }
        int count = bfs(start, 'G');
        return count;
    }
    public int bfs(int[] start, char target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {start[0],start[1], 0});
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int x = now[0];
            int y = now[1];
            int count = now[2];
            visited[x][y] = true;
            
            if(map[x][y] == target) return count;
            
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                boolean flag = true;
                //벽끝까지 or 장애물 만날때까지 이동하기
                while(flag) {
                    if(nx >= 0 && ny >= 0 && nx < map.length && ny < map[0].length && map[nx][ny]!= 'D') {
                        nx += dx[i];
                        ny += dy[i]; 
                    } else {
                        flag = false;
                    }
                }
                //벽에 박기전 or 장애물 만나기 직전상태..!
                nx -= dx[i];
                ny -= dy[i];
                              
                if(visited[nx][ny] || nx == x && ny == y) continue;
                visited[nx][ny] = true;
                queue.add(new int[] {nx, ny, count+1});
            }
        }
        return -1;
    }
}