프로그래머스 level2 : 리코쳇 로봇 - Java

 

BFS로 풀수 있는 문제이다.

항상 문제를 제대로 읽어야한다. 갈수 있는 상하좌우 방향으로 한칸씩 도는게 아니고..

모든방향을 장애물이나 맨끝에 부딪힐때까지 미끄러져서 가는 것이 한번의 이동이다.

따라서 (0,0)에서 아래방향으로 가는데 장애물이 없어서 맨끝인 (n,0)까지 미끄러진다하면 (0,0)에서 (n,0)까지 가는것이 한번의 이동인 것이다.

또한, 목표물인 G까지 도달하는 것도 이 원칙이 적용 되어서 G의 상하좌우에 장애물있거나 G가 맨끝에 위치하는 경우에만  G에 도착이 가능하다. 

 

import java.util.*;

class Solution {
    
    private final int[] dx = {-1,1,0,0};
    private final int[] dy = {0,0,-1,1};
    
    private final char ROBOT = 'R', DISABLE = 'D', GOAL = 'G';
    
    private int n, m;
    
    private class Moving{
        int x,y,depth;
        
        public Moving(int x, int y, int depth){
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
    
    public int solution(String[] board) {
        int answer = 0;
        
        n = board.length;
        m = board[0].length();
        
        Moving robot = null;
        Moving goal = null;
        
        // R이랑 G 좌표 찾기
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                char ch = board[i].charAt(j);
                
                if(ch == ROBOT){
                    robot = new Moving(i,j,0);
                }else if(ch == GOAL){
                    goal = new Moving(i,j,0);
                }
            }
        }
        
        // bfs 돌리면서 최소 경로 길이 찾기
        answer = bfs(board, robot, goal);
        
        return answer;
    }
    
    private int bfs(String[] board, Moving robot, Moving goal){
        Queue<Moving> q = new LinkedList<>();
        // 시작점을 큐에 넣음
        q.add(robot);
        boolean[][] visited = new boolean[n][m];
        visited[robot.x][robot.y] = true;
        
        while(!q.isEmpty()){
            Moving now = q.poll();
            
            // 현재 노드가 goal일때
            if(now.x == goal.x && now.y == goal.y){
                return now.depth;
            }
            
            // 현재 노드가 goal이 아닐때 
            // 현재노드에서 미끄러져서 갈수 있는 모든 노드들을 구해서 q에 넣기
            // 그 노드들이 goal인지 아닌지인 그 노드아 queue의 맨앞에서 poll될때 체크.
            for(int i = 0; i < 4; i++){
                // 지금 노드에서..
                int nx = now.x;
                int ny = now.y;
                
                // 한방향으로 장애물이나 맨 끝에 부딪힐때까지 쭉 미끄러지기
                while(inRange(nx, ny) && board[nx].charAt(ny) != DISABLE){
                    nx += dx[i];
                    ny += dy[i];
                }
                
                // 막히기 직전 노드로 세팅
                nx -= dx[i];
                ny -= dy[i];
                
                // 방문한 곳이거나 움직임이 없으면 다음 방향으로~
                if(visited[nx][ny] || (now.x == nx && now.y == ny)) continue;
                
                visited[nx][ny] = true;
                // 지금 노드를 큐에 넣음
                // depth는 기존 노드의 depth에 +1 만함 
                // 왜? 쭉 미끄러지는게 한번의 움직임이라서~
                q.add(new Moving(nx, ny, now.depth + 1));
            }
        }
        
        return -1;
        
    }
    
    private boolean inRange(int x, int y){
        return x >= 0 && y >= 0 && x < n && y < m;
    }
}