[프로그래머스] Lv.2 - 리코쳇 로봇 - JAVA

문제

리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

 

제한사항

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

 

입출력 예시

 

풀이

DFS를 사용해서 보드판의 끝이나 장애물을 만난 경우 멈추고 해당 위치의 이동 횟수를 기록해두는 방식으로 풀이했다.

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

class Solution {
    public int solution(String[] board) {
        String[][] map = new String[board.length][board[0].length()];
        boolean[][] visited = new boolean[board.length][board[0].length()];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int[] start = new int[2];

        for(int i = 0; i<board.length; i++) {
            String[] tmp = board[i].split("");

            for(int j = 0; j<tmp.length; j++) {
                map[i][j] = tmp[j];

                if (tmp[j].equals("R")) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }

        // BFS 시작점
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;

        while(!queue.isEmpty()) {
            int[] q = queue.poll();
            System.out.println(Arrays.toString(q));
            int y = q[0];
            int x = q[1];
            int cnt = q[2];

            // 상하좌우 4가지 이동
            for(int i = 0; i < 4; i++) {
                int nx = x;
                int ny = y;

                // 끝까지 이동 ( 보드를 넘어가거나, 장애물에 부딪힐 때 stop )
                while(true) {
                    if ( ny < 0 || ny >= map.length || nx < 0 || nx >= map[0].length ) {
                        break;
                    }

                    if (map[ny][nx].equals("D")) {
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }

                    nx += dx[i];
                    ny += dy[i];
                }

                // 보드를 넘어갈 경우, 방향에 따라 위치 재조정
                if ( ny < 0 || ny >= map.length || nx < 0 || nx >= map[0].length ) {
                    if (i == 0 ) {
                        nx = map[0].length - 1;
                    } else if (i == 1) {
                        nx = 0;
                    } else if (i == 2) {
                        ny = map.length - 1;
                    } else {
                        ny = 0;
                    }
                }

                if (map[ny][nx].equals("G")) {
                    return cnt + 1;
                }

                if (!visited[ny][nx]) {
                    queue.add(new int[]{ny, nx, cnt + 1});
                    visited[ny][nx] = true;
                }
            }
        }
        return -1;
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.