(코테) 프로그래머스_리코쳇 로봇 * bfs

리코쳇 로봇

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

 

 

 

import java.util.*;
class Solution {
    int[] x = {-1,1,0,0};
    int[] y = {0,0,-1,1};
    int height;
    int width;
    boolean[][] visted ;
    public int solution(String[] board) {
        int answer = -1;
         height = board.length;
         width = board[0].length();
        char[][] map = new char[height][width];
        visted = new boolean[height][width];
        
        int[] startIndex = new int[2];
        for(int i =0;i<height;i++){
            for(int j =0;j<width;j++){
                map[i][j] = board[i].charAt(j);                              
                if(board[i].charAt(j)=='R'){
                    startIndex[0] =i;
                    startIndex[1] =j;
                }
            }
        }
        
       answer = bfs(startIndex,map);
        
        
        //미끄러짐 필요
        
        return answer;
    }
    
    public int bfs(int[] startIndex,char[][] map){        
        Queue<int[]> q= new LinkedList<>();
        q.offer(new int[]{0,startIndex[0],startIndex[1]});
        visted[startIndex[0]][startIndex[1]]=true;
        
        while(!q.isEmpty()){
            int[] current =q.poll();
            int count=current[0];
            int nowX=current[1];
            int nowY=current[2];

            //종료 조건                                        

            
            if(map[nowX][nowY]=='G') return count; 
            
             for(int i=0;i<4;i++){
                int nextX = nowX;
                int nextY = nowY;
                 
                //int tempNowX;                 
                //int tempNowY;
                 //슬라이딩
                while(true){                                                         
                    int tempNowX = nextX + x[i];
                    int tempNowY = nextY + y[i];   
                    //멈춤 조건
                    if(tempNowX<0  || tempNowY<0 || tempNowX>height-1 || tempNowY>width-1) break;
                    if(map[tempNowX][tempNowY]=='D') break;  
                    
                    nextX =tempNowX;
                    nextY =tempNowY;                 
                }                
                 
                 if((nextX != nowX || nextY!=nowY) && !visted[nextX][nextY]){
                 visted[nextX][nextY]=true;
                 
                 q.offer(new int[]{count+1 , nextX , nextY});    
                 }                                     
             }            
        }
        
        return -1;
    }
}

 

 

회고.

1. 해당 문제는 정석 bfs에  +  장애물에 걸리지 않는다면 해당 방향으로 반복해서 진행하는 방식으로 

while문 안에 while문을 넣어 장애물에 걸릴때까지 진행방향으로 진행 후 장애물 걸리면 count 증가시킨 후 새로운 q에 넣는 방식이다