[프로그래머스,Java] Level2: 리코쳇 로봇

 

문제분석 : 

 

문제 푸는 전략은 쉽게 생각할수 있지만,  구현하다보면 빡코딩이 된다.

 

그래서 만약, 이 문제를 못풀면 심한 자괴감이 들수있다.

그야.. 푸는 방법은아는데 구현을 못하면 그만큼 억울한 상황이 없으니..

 

 

1. BFS 전략 사용하기

 

2. BFS 전략을 사용하여 최소거리를 구하는건 맞되,  리코쳇 로봇은 벽 , 장애물을 부딪힐때까지 움직인다.

 

즉, 원래 BFS는  4방향으로 1칸씩 움직여 도착하는 장소를 결정하지만,

이 문제는 4방향으로 몇칸씩 움직일지 매순간 미지수이므로, 움직여 도착하는 장소를 세밀하게 개선해야한다.

 

 

요약하자면 BFS전략에  이동하는 로직만 변경하면되는데,

 

막상 코딩을해보면 많이 버겁다.

 

 

문제풀이:

 

 

BFS의 기초 

 

방문체크와  Que를 선언했다.

 

방문체크는  재 방문을통해 무한루프를 방지함이고,  Que의 특성을 사용해 최소거리를 판별할수있다.

 

 

스타팅 포인트 설정

 

이 문제는 로봇의 시작지점이 고정적이지않고,  미로마다 다르기때문에 탐색하여 설정해줘야한다.

 

que의 집어넣는건  Y , X 좌표와  Level이다.

 

집어넣을때 방문체크를 깜빡하지말고 하자.  다시 스타팅 포인트로 돌아오면 무한루프가 일어난다.

 

Level을 통하여 최소거리를 판별한다. 

 

 
        while(!que.isEmpty()){
            
            int[] q =que.poll();
            
            int y = q[0];
            int x = q[1];
            int level = q[2];
            
            if(board[y].charAt(x)=='G'){
                return level;
            }
            
            // x,y증분
            int dx=1;
            int dy=1;
            
            // Right
            while(x+dx!=x_size&&board[y].charAt(x+dx)!='D'){
                
                // if(x+dx==x_size||board[y].charAt(x+dx)=='D'){
                //     break;
                // }
                
                dx++;            
            }
            
            if(!visited[y][x+dx-1]){
                que.add(new int[]{y,x+dx-1,level+1});
                visited[y][x+dx-1]=true;
            }
            
            dx=1;
            
            //UP
            while(y-dy!=-1&&board[y-dy].charAt(x)!='D'){
                dy++;
            }
            
            if(!visited[y-dy+1][x]){
                que.add(new int[]{y-dy+1,x,level+1});
                visited[y-dy+1][x]=true;
            }
            dy=1;
            
            //Left
            while(x-dx!=-1&&board[y].charAt(x-dx)!='D'){
                dx++;
            }
            
            if(!visited[y][x-dx+1]){
                que.add(new int[]{y,x-dx+1,level+1});
                visited[y][x-dx+1]=true;
            }
            dx=1;
            
            //Down        
            while(y+dy!=y_size&&board[y+dy].charAt(x)!='D'){
                dy++;
            }                     
            if(!visited[y+dy-1][x]){
                que.add(new int[]{y+dy-1,x,level+1});
                visited[y+dy-1][x]=true;
            }
            dy=1;
            
            
        }

 

이제부터 4방향으로 집어넣는 로직이다.

 

기초적으로,  Queue에서 원소를뽑을때 그 원소가  Goal 목표인지 확인한다.

 

목표면 바로 값을 반환시켜주면된다.

 

목표가 아니면  4방향으로 Queue를 집어넣는다. 

 

4방향의 로직은 서로 비슷하니 

 

Right 로직만 살펴보겠다.

 

Right로직은,  x를 1만큼 계속 증가시켜서,   벽에 부딪히거나, 장애물에 부딪히면 그만해야한다.

 

근데 1만큼 계속 증가시키는 행위는 잠깐만 사용해야할거니, dx라는 증분 변수를 사용한다.

잠깐만 사용해야하는 이유는 다음 Up,Left할때 그값을 그대로 사용하면 안되기 때문이다.

 

벽에 부딪히거나 장애물에 부딪히면 Stop!

 

이걸 코드로 표현하면  

 if(x+dx==x_size||board[y].charAt(x+dx)=='D') 코드다.

 

이 코드를 반대로 쓰면, 

x+dx!=x_size&&board[y].charAt(x+dx)!='D' 코드다. 

 

반대로쓴 코드를  while()문에 조건에 넣어주면 조금 가독성이 높아진다.

 

계속 증분을 시켜서 벽과 장애물에 부딪히면,

Que에다 벽과 장애물에 부딪히기 전의 장소를 집어넣는다.

 

단, 방문을 안했을때의 경우다.  이미 방문한 경우는 넣지말자.

 

하나의 탐색이 완료댔으면 썻던 증분은 다시 초기화해주자.

 

 

전체코드

 
    import java.util.*;class Solution {
    public int solution(String[] board) {
        int answer = -1;
     
        int y_size= board.length;
        int x_size= board[0].length();
        
        boolean[][] visited = new boolean[y_size][x_size];
        
        Queue<int[]> que = new LinkedList<>();
        
        for(int i=0;i<y_size;i++){
            for(int j=0;j<x_size;j++){
                if(board[i].charAt(j)=='R'){
                    // y ,x , level
                    que.add(new int[]{i,j,0});
                    visited[i][j]=true;
                }
            }
        }
        
        while(!que.isEmpty()){
            
            int[] q =que.poll();
            
            int y = q[0];
            int x = q[1];
            int level = q[2];
            
            if(board[y].charAt(x)=='G'){
                return level;
            }
            
            // x,y증분
            int dx=1;
            int dy=1;
            
            // Right
            while(x+dx!=x_size&&board[y].charAt(x+dx)!='D'){
                
                // if(x+dx==x_size||board[y].charAt(x+dx)=='D'){
                //     break;
                // }
                
                dx++;            
            }
            
            if(!visited[y][x+dx-1]){
                que.add(new int[]{y,x+dx-1,level+1});
                visited[y][x+dx-1]=true;
            }
            
            dx=1;
            
            //UP
            while(y-dy!=-1&&board[y-dy].charAt(x)!='D'){
                dy++;
            }
            
            if(!visited[y-dy+1][x]){
                que.add(new int[]{y-dy+1,x,level+1});
                visited[y-dy+1][x]=true;
            }
            dy=1;
            
            //Left
            while(x-dx!=-1&&board[y].charAt(x-dx)!='D'){
                dx++;
            }
            
            if(!visited[y][x-dx+1]){
                que.add(new int[]{y,x-dx+1,level+1});
                visited[y][x-dx+1]=true;
            }
            dx=1;
            
            //Down        
            while(y+dy!=y_size&&board[y+dy].charAt(x)!='D'){
                dy++;
            }                     
            if(!visited[y+dy-1][x]){
                que.add(new int[]{y+dy-1,x,level+1});
                visited[y+dy-1][x]=true;
            }
            dy=1;
            
            
        }
        
        return answer;
    }
}