프로그래머스 - 리코쳇 로

문제

https://www.acmicpc.net/problem/169199

풀이

• BFS를 이용하여 장애물을 만나거나 끝에 도달한 경우 다른 방향으로 탐색하게 한다.

유의할 점

• 일반적인 bfs와 다르게 한 칸씩 움직여서 계산하지 않고 이동이 불가능할 때까지 움직인 다음 계산을 해야 함

코드

import java.util.*; 
class Solution {
    static int n,m; 
    static int[] dx ={-1,0,1,0};
    static int[] dy = {0,-1,0,1}; 
    static int[][] visited; 
    static Queue<int[]> q; 
    static int[] dest = new int[2]; 
    static int answer =-1; 
    public int solution(String[] board) {
        q = new LinkedList<>(); 
        n = board.length; 
        m= board[0].length();
        visited = new int[n][m]; 
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i].charAt(j)=='R') {
                    q.add(new int[]{i,j});
                    visited[i][j]= 1; 
                }else if (board[i].charAt(j)=='G'){
                    dest[0]= i;
                    dest[1]= j;
                }
            }
        }
        
        while(!q.isEmpty()){
            int[] curr = q.poll(); 
            for(int i=0; i<4; i++){
                move(curr[0], curr[1], i,board); 
            }
        }
        return answer==-1 ? -1 : answer-1;
    }

    static void move (int x, int y, int dir,String[] board){
        int nx = x;
        int ny = y; 
        while(0<= nx+dx[dir] && nx+dx[dir]<n && 0<=ny+dy[dir] && ny+dy[dir]<m && board[nx+dx[dir]].charAt(ny+dy[dir])!='D') {
            nx+=dx[dir]; 
            ny+=dy[dir]; 
        }
        if(visited[nx][ny]==0){
             q.add(new int[]{nx,ny}); 
            visited[nx][ny] = visited[x][y]+1; 
            if(nx ==dest[0] && ny==dest[1]) {
               answer = visited[nx][ny];
                return;
            }
        } 
    }
}