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

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

프로그래머스

 

:: 간만에 풀었던 BFS 그래프 문제

:: 상화좌우 이동을 잘 구현하는 것이 핵심이었던 것 같다.

 

import java.util.*;
import java.awt.Point;
 
class Solution {
    //상, 하, 좌, 우
    int []dx = {-1,1,0,0};
    int []dy = {0,0,-1,1};
    
    public int solution(String[] board) {
        int answer = -1;
        int row = board.length;
        int col = board[0].length();
        
        Queue<Point> q = new LinkedList<Point>();
        int [][]map = new int[row][col];
        int start_row = 0, start_col = 0;
        int end_row = 0, end_col = 0;
        
        //setting into integer map
        for(int i=0 ; i < row ; i++){
            for(int j=0 ; j < col ; j++){
                if(board[i].charAt(j) == 'R'){
                    start_row = i;
                    start_col = j;
                    q.add(new Point(i,j));
                }else if(board[i].charAt(j) == 'D'){
                    map[i][j] = -1;
                }else if(board[i].charAt(j) == 'G'){
                    end_row = i;
                    end_col = j;
                }
            }
        }
        
        while(!q.isEmpty()){
            Point p = q.poll();
            int x = p.x, y = p.y;
            
            for(int i=0 ; i<4 ; i++){
                int nx = x, ny = y;
                
                while(nx + dx[i] >= 0 && nx + dx[i] < row && ny + dy[i] >= 0 && ny + dy[i] < col 
                    && map[nx+dx[i]][ny+dy[i]] != -1){
                    nx += dx[i];
                    ny += dy[i];
                }
                
                if(nx == start_row && ny == start_col) continue;
                if(map[nx][ny] == 0){
                    q.add(new Point(nx,ny));
                    map[nx][ny] = map[x][y] + 1;
 
                    if(nx == end_row && ny == end_col){
                        return map[nx][ny];
                    }
                }
            }
        }
        
        return answer;
    }
    
    
}