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

 

리코쳇로봇

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.

시작에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하 , 좌 , 우 4방향 으로 이동할 수 있으며 미끄러져 이동하는 것을 한번의 이동으로 칩니다.

 

위 그림 처럼 R에서 시작해 "D" 혹은 벽에 부딪힐 떄 까지 가는겁니다. "." 빈 공간을 의미합니다.

만약 위치에 도달할수 없다면 -1을 return 합니다.

 

import java.util.*;

class Solution {
    static class State{
        int x, y, moves;
         State(int x , int y, int moves){
            this.x = x;
            this.y = y;
            this.moves = moves;
        }
    }
    
    public int solution(String[] board) {
        int answer = 0;
        
        int startX = 0 , startY = 0;
        int endX=0, endY =0;
        
        Queue<State> que = new LinkedList<>();
        
        int rows = board.length;
        int cols = board[0].length();
        
        //이동 방향 기억
        boolean[][][] boardTemp = new boolean[rows][cols][4];
        
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                if(board[i].charAt(j) == 'R'){
                    startX = i;
                    startY = j;
                }else if(board[i].charAt(j) == 'G'){
                    endX = i;
                    endY = j;
                }
            }
        }
        
        int[][] directions = {{0,1} , {1,0},{-1,0},{0,-1}}; //우 , 하 , 상 , 좌
        
        //큐 초기화
        que.add(new State(startX , startY , 0));
        
        while(!que.isEmpty()){
            State current = que.poll();
            
            // G일 경우 return
            if(current.x == endX && current.y == endY){
                return current.moves;
            }
            
            for(int i=0; i< directions.length; i++){
                
                int nextX = current.x;
                int nextY = current.y;
                int x = directions[i][0];
                int y = directions[i][1];
                
                // 되는 방향까지 간 다음 큐에 넣기
                while(true){
                    nextX += x;
                    nextY += y;
                    if(nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols || board[nextX].charAt(nextY) == 'D'){
                        nextX -= x;
                        nextY -= y;
                        break;
                    }
                }    
                if( !boardTemp[nextX][nextY][i] && !( nextX == current.x && nextY == current.y)){
                    boardTemp[nextX][nextY][i] = true;
                    que.add(new State(nextX , nextY , current.moves+1));
                }
            }
        }
        
        return -1;
    }
}

 

 

진행

큐에서 'State(0 , 6, 0)' 을 꺼냅니다. 이 위치에서 로봇은 4가지 방향으로 이동을 시도 할 수 있습니다.

그렇게 되면 큐에는 'State(2, 6, 1)' 과 'State(0, 4, 1)' 이 추가 됩니다.

이 상태들은 이동한 방향이동 한 후 멈춘 위치에 도달할 때 까지 의 이동 회수도 같이 저장합니다.

모든 방향으로 진행을 하다가 제일 먼저 도착한 진행 상태를 return 하여 최소 회수를 반환하는 것 입니다.

 

BFS 탐색

BFS는 큐에 있는 각 상태를 하나씩 꺼내어 다음 가능한 모든 이동을 탐색합니다. 로봇은 각 방향으로 이동할 때 장애물 바로 앞에서 멈추어야 하며, 이렇게 이동한 후의 새로운 위치를 큐에 추가합니다.

 

이렇듯 BFS 는 최단 경로를 찾거나, 노드와 노드 사이의 최소 간격을 구할 떄 유리합니다. 또한, 래밸 별로 탐색을 진행하기 때문에 문제의 특성에 따라 BFS가 더 적합합니다.

 만약 모든 경로를 탐색을 하게 되면 최단 경로를 알 수는 있더라 하더라도.. 더 많은 시간이 소요될 수 있습니다.

 

아래는 BFS 의 간단하게 구현한 예시입니다.

 

import java.util.*;

public class BFSExample {
    public static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.println("Visited: " + node);

            for (int nextNode : graph.get(node)) {
                if (!visited[nextNode]) {
                    queue.offer(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        boolean[] visited = new boolean[5];  // 간단한 예시를 위해 노드는 5개라고 가정

        // 그래프 초기화
        for (int i = 0; i < 5; i++) {
            graph.add(new ArrayList<>());
        }
        // 그래프의 간선 설정
        graph.get(0).add(1);
        graph.get(1).add(2);
        graph.get(2).add(3);
        graph.get(3).add(4);

        bfs(0, graph, visited);  // 0번 노드부터 탐색 시작
    }
}