프로그래머스 스쿨(Java - Lv.2) - 리코쳇 로봇[BFS]

문제

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

프로그래머스

 

 

해답

import java.util.*;

class Solution {
    String[][] board;
    boolean[][] visited;
    Queue<int[]> que = new LinkedList<>();
    int[] goal;
    int[] start;
    int answer = 1;
    int cnt = 1;
    public int solution(String[] p_board) {
        //변수로 받은 string 배열을 2차원으로 전환하며 도착과 시작지점 기록
        board = new String[p_board.length][p_board[0].length()];
        visited = new boolean[board.length][board[0].length];
        for(int i=0;i<p_board.length;i++){
            String[] splboard = p_board[i].split("");
            for(int j=0;j<splboard.length;j++){
                board[i][j] = splboard[j];
                if(board[i][j].equals("G")){
                    goal = new int[]{i,j};
                }
                if(board[i][j].equals("R")){
                    start = new int[]{i,j};
                }
            }
            
        } 
        //bfs탐색시작
        que.add(start);
        while(!que.isEmpty()){
            int size = que.size();
            for(int i=0;i<size;i++){
                bfs();
                if(answer!=1)
                    return answer;
            }
            cnt++;
        }
        return -1;
    }
    //상하좌우 끝까지 이동하며 진행할 bfs
    public void bfs(){
        int[] current = que.poll();
        visited[current[0]][current[1]] = true;
        int currentR = current[0];
        int currentC = current[1];
        //System.out.println("bfs> R="+current[0]+" C="+current[1]+" cnt="+cnt+" answer="+answer);
        move(currentR, currentC, 1, 0);
        if(answer!=1) return;
        move(currentR, currentC, 0, 1);
        if(answer!=1) return;
        move(currentR, currentC, -1, 0);
        if(answer!=1) return;
        move(currentR, currentC, 0, -1);
        if(answer!=1) return;
    }
    
    public void move(int startR, int startC, int dr, int dc){
        while(startR>=0 && startC>=0 && startR<board.length && startC<board[0].length){ //범위 안에 있을때
            startR+=dr;
            startC+=dc;
            
            if(startR==-1 || startC ==-1 || startR==board.length || startC==board[0].length
              || board[startR][startC].equals("D")){ //끝에닿을때
                if(!visited[startR-dr][startC-dc]){
                    visited[startR-dr][startC-dc] = true;
                    que.add(new int[]{startR-dr,startC-dc});
                }
                if(board[startR-dr][startC-dc].equals("G")){
                    answer = cnt;
                    return;
                }
                return;
            }       
        }
        
    }
}

 

 

해설

 

전형적인 bfs로 최단 depth가 몇인지 구하는 문제였다.

 

초반에 주어진 배열을 2차원 배열로 처리하여 4방향으로 끝까지 움직이는것을 일일히 구현하지않고, 덧셈을할때 어떻게 할지를 고민하여 범위를 벗어날때나 장애물을 만날때 그전의 위치를 도달 위치로 체크하였다.

 

개인적으로 코드가 너무 길어진것으로 보여 시간초과는 없었으나, 가독성면에서 좀 더 향상시킬방법이 없나 고민해봐야겠다.