[BFS] 리코쳇 로봇

접근

리코쳇 로봇

이 문제는 백준의 배추벌레와 비슷한 문제입니다.
그 문제는 배추가 있을 때 전진했고 상하좌우로 다 가능하지만

이 문제는 상하좌우로 이동이 가능하지만
장애물이나 벽에 부딪히기 전까지는 계속 한 방향으로 전진한다는 차이점이 있습니다.
사실 로봇 청소기를 생각하면 쉬울거 같습니다.
로봇청소기도 계속 나아가다 장애물을 만나면 turn을 하기 때문입니다.

문제에 주어진 예시를 그림으로 표현해보았습니다.

위와 같이 "."으로 된 곳으로 이동이 가능하고 D를 만나면 방향을 바꿀 수 있도록 하는 조건문,
그리고 하나의 상태배열이 필요합니다.
저의 경우 D를 중심으로

상하좌우를 check하며 들렸던 곳인지 아닌지를 판단했습니다.

풀이

import java.util.*;

class Solution {
    static int[] nx = {-1,1,0,0};
    static int[] ny = {0,0,-1,1};
    
    static char[][] pan;
    static int min = Integer.MAX_VALUE;
    static boolean[][] visited;
    
    static class XY{
        int x;
        int y;
        int cnt=0;
        public XY(int x, int y, int cnt){
            this.x=x;
            this.y=y;
            this.cnt=cnt;
        } 
    }
    
    public int solution(String[] board) {
        int answer = 0;
        
        pan= new char[board.length][board[0].length()];
        
        XY start = new XY(0,0,0);
        
        for(int i=0;i<board.length;i++){
           for(int j=0;j<board[0].length();j++){
               char target = board[i].charAt(j);
               pan[i][j] =target;
               if(target=='R'){
                   start = new XY(i,j,0);
               }
           }
        }
       
        visited= new boolean[pan.length][pan[0].length];
        
     
         bfs(start);
        
        if(min==Integer.MAX_VALUE) return -1;
        
        return min;
    }
    
    static void bfs(XY start){
        Queue<XY> q = new LinkedList<>();
        q.offer(start);
        
        while(!q.isEmpty()){
            
            XY robot = q.poll();
            
            if(pan[robot.x][robot.y]=='G'){
                if(min>robot.cnt){
                    min=robot.cnt;
                }
            }
            
            for(int i=0;i<4;i++){
                
                int j=0;
                
                int newX = 0;
                int newY = 0;
                
                // newX와 newY는 판의 범위까지
                // 만약에 D이면 스톱 
                while(true){
                     j++;
                     newX = robot.x + nx[i]*j;
                     newY = robot.y + ny[i]*j;
                     if(newX>=0 && newX <pan.length && newY >=0 && newY <pan[0].length){
                         if(pan[newX][newY]=='D') break;
                     }else break;
                }
                
              //  System.out.println(robot.x+nx[i]*(j-1)+","+robot.y+ny[i]*(j-1));
                if(!visited[robot.x+nx[i]*(j-1)][robot.y+ny[i]*(j-1)]){
                   q.offer(new XY(robot.x+nx[i]*(j-1),robot.y+ny[i]*(j-1), robot.cnt+1));
                   visited[robot.x+nx[i]*(j-1)][robot.y+ny[i]*(j-1)]=true;
                }
                    
            } //for
            
        }//while
        
    }
    
    
    
}