프로그래머스 - 리코쳇 로봇(Java)

bfs 문제입니다.

 

최소로 움직이는 횟수를 구하는 문제이기 때문에 bfs를 사용해야 한다는 것을 알 수 있습니다.

 

이 문제는 로봇이 상, 하, 좌, 우로 움직이되 벽이나 장애물(D)을 만나야 움직임을 멈춤니다.

while (inRange(nx, ny) && board[nx].charAt(ny) != 'D') {
    nx += dx[i];
    ny += dy[i];
}

 

즉, 지나가는 경로에 골인(G) 지점이 있더라도 도착한 것이 아닙니다.

로봇이 멈추는 곳이 골인 지점이여야만 합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};

    private final char ROBOT = 'R', DISABLE = 'D', GOAL = 'G';

    private int n, m;

    private class Moving {
        int x, y, depth;

        public Moving(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }

    public int solution(String[] board) {
        int answer = 0;

        n = board.length;
        m = board[0].length();

        Moving robot = null;
        Moving goal = null;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch = board[i].charAt(j);

                if (ch == ROBOT) {
                    robot = new Moving(i, j, 0);
                } else if (ch == GOAL) {
                    goal = new Moving(i, j, 0);
                }
            }
        }

        answer = bfs(board, robot, goal);

        return answer;
    }

    private int bfs(String[] board, Moving robot, Moving goal) {
        Queue<Moving> qu = new LinkedList<>();
        qu.add(robot);
        boolean[][] visited = new boolean[n][m];
        visited[robot.x][robot.y] = true;

        while (!qu.isEmpty()) {
            Moving cn = qu.poll();

            if (cn.x == goal.x && cn.y == goal.y) {
                return cn.depth;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cn.x;
                int ny = cn.y;

                // 범위를 벗어나거나 장애물을 만날 때 까지 반복
                while (inRange(nx, ny) && board[nx].charAt(ny) != DISABLE) {
                    nx += dx[i];
                    ny += dy[i];
                }

                // 범위를 벗어나거나 장애물 만나기 '직전'의 상태
                nx -= dx[i];
                ny -= dy[i];

                // 방문을 하거나 같은 위치일 경우 스킵
                if (visited[nx][ny] || (cn.x == nx && cn.y == ny)) continue;

                visited[nx][ny] = true;
                qu.add(new Moving(nx, ny, cn.depth + 1));
            }
        }

        return -1;
    }

    private boolean inRange(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m;
    }
}