[프로그래머스/JAVA] 169199번 리코쳇 로봇 (BFS)

문제

문제 링크

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

프로그래머스

 

 

문제 설명

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

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

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

예시 이미지

 

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

만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

 

제한 사항

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

 

입출력 예시

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

 

 

 

문제 풀이

 

접근 방법

• 한번 움직임의 정의
  • 상하좌우 방향으로 이동불가 할때까지 이동하는 것을 의미
• 보드판을 입력받아서 BFS 로 시작지점에서 목표지점까지 탐색
• 목표지점에 도달할수 없을 경우 -1 반환

 

코드

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

public class P_169199 {

    // 이동 범위
    static int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // 장애물 맵
    static char[][] map;

    // 시작지점, 목표지점
    static int sX, sY, gX, gY;

    // 보드판 크기
    static int rows, cols;

    private static int solution(String[] board) {
        rows = board.length;
        cols = board[0].length();

        // 보드판 맵핑, 시작지점, 종료지점 찾기
        map = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            map[i] = board[i].toCharArray();
            for (int j = 0; j < cols; j++) {
                if (map[i][j] == 'R') {
                    sX = i;
                    sY = j;
                }

                if (map[i][j] == 'G') {
                    gX = i;
                    gY = j;
                }
            }
        }

        // BFS 탐색
        return bfs();
    }

    private static int bfs() {
        // 방문 확인 배열
        boolean[][] visited = new boolean[rows][cols];

        // BFS 큐
        Queue<int[]> queue = new LinkedList<>();

        // 시작점 초기화
        queue.add(new int[]{sX, sY, 0});
        visited[sX][sY] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            for (int[] move : moves) {

                // x, y, 이동 횟수
                int x = cur[0];
                int y = cur[1];
                int count = cur[2];

                // 이동: 장애물('D')를 만나거나 가장자리까지 이동
                while (isInBounds(x+move[0], y+move[1]) && map[x+move[0]][y+move[1]]!='D') {
                    x += move[0];
                    y += move[1];
                }

                // 이동 횟수 추가
                count++;

                // 목표지점 도달시 이동 횟수 반환
                if (x == gX && y == gY) {
                    return count;
                }

                // 방문 처리 및 다음 탐색 노드 추가
                if (!visited[x][y]) {
                    visited[x][y] = true;
                    queue.add(new int[]{x, y, count});
                }
            }
        }

        // 도달불가시 -1 반환
        return -1;
    }

    private static boolean isInBounds(int x, int y) {
        return 0 <= x && x < rows && 0 <= y && y < cols;
    }
}