[프로그래머스] 리코쳇 로봇 (java)

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

프로그래머스

리코쳇 로봇 문제

보드판에서 R부터 시작해서 장애물이나 벽에 도달할 떄 까지 슬라이딩하는 과정을 반복해서 G에 도착하는 최소 값을 구하는 문제

 

#사용 알고리즘

너비 우선 탐색(BFS)

📌문제 접근 포인트

1. 벽을 만날 때까지 미끄러지는 점을 제외하곤 일반 BFS 구현 문제와 동일하다. BFS에서 미끄러지도록 이동하게만 구현해주면 된다.

2. 단순 BFS를 생각했을때 한쪽 방향으로 끝까지 이동할 수 있도록 while 문을 구성해주자. 이 때, 장애물이나 밖으로 나가버리는 위치를 (i+1)이라 하면, 실제 로봇이 도착하는 위치는 i이다.

3. 도착한 i 지점에 대해서 BFS 방문 처리를 해주고, 다시 i 지점에서부터 같은 방식으로 탐색하도록 구현해주면 된다.

반응형

⚙ 내가 푼 정답 코드

import java.util.*;

class Solution {
    public static int n, m;
    public static int[] dy = {-1, 1, 0, 0};
    public static int[] dx = {0, 0, 1, -1};
    public static int[][] visited;
    
    static class board{
        int y, x;
        public board (int y, int x){
            this.x = x;
            this.y = y;
        }
    }
    
    public static int find(String[] boards, int a, int b){
        Queue<board> queue = new LinkedList<board>();
        queue.offer(new board(a,b));
        visited[a][b] = 1;
        while(!queue.isEmpty()){
            board p = queue.poll();
            for(int i = 0 ; i < 4; i++){
                int t = 0;
                while(true){
                    int ny = p.y + (t+1)*dy[i]; // 벽의 위치 i+1
                    int y = p.y + t*dy[i]; // 로봇의 도착 위치 i
                    int nx = p.x + (t+1)*dx[i];
                    int x = p.x + t*dx[i];
                    // i+1 지점이 장애물 이거나, 끝 벽에 만날 경우 실제 위치 i 값을 BFS 탐색
                    if(ny < 0 || ny >= n || nx < 0 || nx >= m || boards[ny].charAt(nx) == 'D'){
                        if(visited[y][x] == 0){
                            visited[y][x] = visited[p.y][p.x] + 1;
                            queue.add(new board(y,x));
                        }
                        if(boards[y].charAt(x) == 'G'){
                            return visited[y][x]-1;
                        }
                        break;
                    }
                    t++;
                }
                
            }
        }
        return -1;
    }
    
    public int solution(String[] board) {
        n = board.length;
        m = board[0].length();
        visited = new int[n][m];
        int result = 0;
        for (int i = 0 ; i < n; i++){
            for (int j = 0 ; j < m; j++){
                if (board[i].charAt(j) == 'R'){
                    result = find(board, i, j);
                }
            }
        }
        
        return result;
    }
}