[pro] 프로그래머스 level2 169199 리코쳇 로봇 (Java) - BFS

[문제]

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

프로그래머스

 

[풀이]

GOAL에 도달하는 최소 이동 횟수를 반환하는 BFS 문제.

 

현재 위치에서 상, 하, 좌, 우 4 방향으로 슬라이딩해서 이동할 수 있다. 따라서 범위가 보드를 벗어나지 않고, 장애물 D에 도달하기 전까지 이동시킨다. 이동한 좌표 위치가 처음 위치와 같거나 이미 방문한 위치라면 다른 방향을 탐색하고, 그렇지 않다면 방문 처리 후 q에 넣는다.

 

큐에서 빼낸 좌표값이 G의 좌표값과 일치하면 최소 이동 횟수를 반환한다. G에 도달할 수 없으면 -1을 반환한다.

 

 

[코드]

 

import java.util.*;

class Solution {
    int[] dr = {-1, 0, 1, 0}; //상 우 하 좌
    int[] dc = {0, 1, 0, -1};
    boolean[][] visited;
    public int solution(String[] board) {
        int answer = 0;
        //말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return
        int sr = 0, sc = 0, er = 0, ec = 0;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length(); j++){
                if(board[i].charAt(j)=='R'){
                    sr = i;
                    sc = j;
                }
                else if(board[i].charAt(j)=='G'){
                    er = i;
                    ec = j;
                }
            }
        }
        visited = new boolean[board.length][board[0].length()];
        
        answer = bfs(sr, sc, er, ec, board);
        
        return answer;
    }
    
    public int bfs(int sr, int sc, int er, int ec, String[] board){
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[]{sr, sc, 0}); //r, c, cnt
        visited[sr][sc] = true;
        
        while(!q.isEmpty()){
            int[] p = q.poll();
            int cnt = p[2];
            
            if(p[0]==er && p[1]==ec){
                return cnt;
            }
            
            
            for(int i=0; i<4; i++){
                int d = i;
                int r = p[0];
                int c = p[1];
                while(true){
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if(nr>=board.length || nr<0 || nc<0 || nc>=board[0].length() || board[nr].charAt(nc)=='D'){
                        break;
                    }
                    r = nr;
                    c = nc;
                }
                
                if(r==p[0] && c==p[1]) continue;
                if(visited[r][c]) continue;
                else {
                    q.add(new int[]{r, c, cnt+1});
                    visited[r][c] = true;
                }
            }
            
        }
        
        return -1;
    }
}