프로그래머스 리코쳇 로봇 - 자바

문제

풀이

public class Pro_리코쳇로봇 {
    public int solution(String[] board) {
        int answer = 0;

        // 시작 지점과 끝 지점
        Node start = null;
        Node goal = null;

        // 현재 위치가 방문했는지 여부
        boolean[][] visited = new boolean[board.length][board[0].length()];

        // 상하좌우로 인덱스를 옮기기 위해 더해줄 숫자
        int[] px = {1,0,-1,0};
        int[] py = {0,1,0,-1};

        // 시작지점, 끝 지점 위치 파악
        for(int i = 0; i < board.length; i++){
            for(int y = 0; y < board[i].length(); y++){
                if(board[i].charAt(y) == 'R'){
                    start = new Node(i,y,0);
                }
                if(board[i].charAt(y) == 'G'){
                    goal = new Node(i,y,0);
                }
            }
        }


        // bfs
        Queue<Node> q = new LinkedList<>();
        q.add(start);

        while(!q.isEmpty()){
            Node now = q.poll();
            visited[now.x][now.y] = true;

            // 만약 현재 위치가 목표 지점이라면 현재 이동횟수를 반환
            if(now.x == goal.x && now.y == goal.y){
                return now.depth;
            }

            // 상하좌우로 이동하며 목표지점으로 이동
            for(int i = 0; i < 4; i++){
                int nextX = now.x;
                int nextY = now.y;
                // 한칸씩 이동하는 bfs와 달리 벽을 만나거나, 장애물을 만날 때까지
                // 현재 방향으로 쭉 이동해야 하므로 while 이용
                while(true){
                    nextX += px[i];
                    nextY += py[i];
                    // 벽이나 장애물을 만나면
                    if(nextX < 0 || nextX >= board.length || nextY < 0
                            || nextY >= board[0].length() || board[nextX].charAt(nextY) == 'D'){
                        // 벽이나 장애물을 만나기 직전 위치로 수정 후 break
                        nextX -= px[i];
                        nextY -= py[i];
                        break;
                    }
                }

                // 이동한 위치를 방문한적이 없는 위치라면 탐색을 진행하고 이동횟수를 +1 해줌
                if(!visited[nextX][nextY]){
                    q.add(new Node(nextX,nextY,now.depth+1));
                }
            }
        }



        return -1;
    }


    class Node{
        int x;
        int y;
        int depth;

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

리뷰

bfs를 활용하여 풀어야 하는 문제였다.
다만, 일반적으로 bfs는 한칸씩 이동하며 최단거리를 찾는 알고리즘이라면, 이 문제에서는 한번 이동한 방향으로 벽이나 장애물을 만날 때까지 쭉 이동해야 한다는 차이가 있다.

이 부분 때문에 bfs를 사용한다는건 알겠는데 어떻게 적용해야 할지 떠오르질 않았다.
최단거리를 구하려면 이동했던 위치를 기록을 해야 하는데, 그럼 지나온 한칸 한칸 모든 칸에 방문 여부를 true로 체크해야 하나? 근데 이러면 다른 방향에서 탐색을 진행할 때 아래의 그림처럼 방문한적이 있는 칸을 마주쳐 버리지 않나? 하는 것 때문에 너무 헷갈렸다.

그런데 내가 놓쳤던 부분은 로봇이 장애물이나 벽을 만나야지만 그 위치에 멈춘다는 것이다.
아무리 목표지점'G'에 도달했다 하더라도 벽이나 장애물을 만나지 않은 이상은 그 위치에 멈추지 않고 지나쳐 버린다는 것이다.
즉, 방문 여부는 로봇이 지나온 모든 칸을 뜻하는게 아니라, 벽이나 장애물을 만나 멈추는 지점이 방문 지점이 되는 것이다.

이것을 알고 나서 알고리즘을 적용하는 것은 수월했다.

알고리즘 문제를 풀 때마다 느끼는건데 알고리즘을 문제에 적용하는 것보다 아이디어를 떠올리는게 어려운 것 같다ㅜㅜ