프로그래머스 - 리코쳇 로봇

코드

import java.util.*;

class Solution {
    int[] nx = new int[]{0,0,1,-1};
    int[] ny = new int[]{1,-1,0,0};
    int N,M;
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        
        boolean[][] visited = new boolean[N][M];
        int sx=0,sy=0;
        
        
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++) {
                char c = board[i].charAt(j);
                if (c == 'R') {
                    sx = j;
                    sy = i;
                    break;
                }
            }
        }
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sx,sy,0});
        visited[sy][sx] = true;
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            
            for (int i=0;i<4;i++) {
                int x = cx;
                int y = cy;
       
                while (check(x + nx[i],y + ny[i],visited,board)) {
                    x += nx[i];
                    y += ny[i];
                }
                
                if (board[y].charAt(x) == 'G') {
                    return cur[2]+1;
                }
                
                if (visited[y][x])
                    continue;
                
                queue.offer(new int[]{x,y,cur[2]+1});
                visited[y][x]=true;
            }
        }
        
        
        return -1;
    }
    
    private boolean check(int x, int y, boolean[][] visited, String[] board) {
        return x >=0 && x< M && y>=0 && y<N && board[y].charAt(x) != 'D';
    }
}

풀이

👍bfs를 통해 문제를 해결 할 수 있었습니다. 기존의 bfs와는 다른게 기존에는 한 칸씩 움직였다면 해당 문제에서는 한 방향으로 끝까지 움직인다는 점입니다.

1. 시작위치를 찾습니다. (sx,sy에 저장)
2. visited배열과 queue를 선언해줍니다. bfs를 위한 작업이라고 생각하시면 됩니다.
3. bfs를 시작합니다. 기본적인 bfs를 제외하고 다른 점만 보자면
   while (check(x + nx[i],y + ny[i],visited,board)) {}를 통해 한 방향으로 움직일 수 있을때까지 쭉 이동합니다.
4. 이동 후 목적지라면 값을 반환합니다.
5. 목저지가 아니라면 visited를 검사합니다. 이미 방문한적이 있는 곳이라면 continue로 넘어갑니다. 이미 방문한적이 있다면 더 빠르게 방문한적이 있는 값이기 때문입니다.
6. queue에 값을 넣고 방문처리해줍니다.

출처 : 프로그래머스 - 리코쳇 로봇