[프로그래머스] 리코쳇 로봇

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/169199

이 문제는 bfs를 이용하여 풀 수 있습니다. 처음 문제 이해를 잘못해서 G에서 멈추는 것이라고 생각했는데 "무조건 장애물이나 맵 바깥"에서만 멈춘다는, 즉 문제에 충실하게 해석해야 한다는 점을 배웠습니다ㅎㅎ 이 문제는 백준 구슬탈출2와 풀이가 거의 유사합니다. (https://velog.io/@gale4739/%EB%B0%B1%EC%A4%80-13460-%EA%B5%AC%EC%8A%AC-%ED%83%88%EC%B6%9C2Java) 각 방향에 해당하는 만큼 장애물과 맵 끝에 도달할때까지 while문에서 계속 반복해주고 나온 결과값을 큐에 넣는 bfs방식으로 풀이하였습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int N,M,sy,sx,fy,fx;
    static int[] dy = {1,0,-1,0}, dx = {0,1,0,-1};
    static boolean[][] map;
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        map = new boolean[N][M];
        
        for(int i=0;i<N;i++){
            String str = board[i];
            for(int j=0;j<M;j++){
                if(str.charAt(j) == '.') map[i][j] = true;
                else if(str.charAt(j) == 'G'){
                    map[i][j] = true;
                    fy = i;
                    fx = j;
                }
                else if(str.charAt(j) == 'R'){
                    map[i][j] = true;
                    sy = i;
                    sx = j;
                }
                else map[i][j] = false;
            }
        }
        

        
        
        return bfs();
    }
    
    static int bfs(){
        boolean[][] check = new boolean[N][M];
        check[sy][sx] = true;
        Queue<Robot> queue = new LinkedList<>();
        queue.add(new Robot(sy,sx,0));
        
        while(!queue.isEmpty()){
            Robot curr = queue.poll();
            if(curr.isG()) return curr.cnt;
            
            for(int i=0;i<4;i++){
                Robot next = curr.move(i);
                
                if(!check[next.y][next.x]){
                    check[next.y][next.x] = true;
                    queue.add(next);
                }
            }
        }
        
        return -1;
    }
    
    static class Robot{
        int y;
        int x;
        int cnt;
        
        Robot(int y, int x, int cnt){
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }
        
        Robot move(int dir){
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if(ny<0 || ny>=N || nx<0 || nx>=M) return this;
            
            while(map[ny][nx]){
                ny += dy[dir];
                nx += dx[dir];
                
                if(ny<0 || ny>=N || nx<0 || nx>=M){
                    break;
                }
            }
            
            ny -= dy[dir];
            nx -= dx[dir];
            return new Robot(ny,nx,cnt+1);
        }
        
        boolean isG(){
            return y == fy && x == fx;
        }
    }
}