[프로그래머스] 리코쳇 로봇 / 자바(Java)

• 문제

• 해설

• 주의점

• 코드

문제

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

프로그래머스

 

---

해설

2차원배열에서의 4방탐색과 bfs를 통해 목표까지의 최단 횟수를 구하는 문제입니다.

 

bfs를 구현하기 위해 큐를 사용합니다. 큐에는 특정 좌표(r,c)를 담는 1차원 배열을 넣어줍니다.

여기서 중요한점!

여러번 이동하다 이전에 갔던 곳을 표시하는 boolean 2차원 배열이 필요합니다.

목표까지의 최단 횟수를 구하기 때문에 이전에 갔던 곳을 간다면 목표로 도달하는데 그 곳보다 무조건 더 오래 걸리기 때문에 이전에 갔던 곳은 배제하고 진행해도 됩니다.

이후 4방 탐색을 통해 벽 또는 장애물에 부딪힌 경우 그 앞에 멈춰서 목표인지 확인한 후 큐에 새로운 좌표를 넣어 반복하는 형식으로 모든 가능성을 파악해 봅니다.

주의점

• 진행방향으로 벽 또는 장애물의 '앞' 까지만 진행하고 멈춥니다.

---

코드

import java.util.*;
class Solution {
    public int solution(String[] board) {
        int answer = -1;
        
        // b : board를 2차원char배열로 저장
        char[][] b = new char[board.length][board[0].length()];
        // point : 특정 위치에서 탐색을 했는가 확인(4방탐색을 한 지점인 경우 true)
        boolean[][] point = new boolean[board.length][board[0].length()];
        int[] start = new int[2];
        // 사방탐색용 배열(상, 우, 하, 좌)
        int[] dc = {-1,0,1,0};
        int[] dr = {0,1,0,-1};
        
        // 배열로 저장 및 시작점 저장
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length();j++){
                b[i][j] = board[i].charAt(j);
                if(b[i][j]=='R') {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        
        // bfs를 위한 큐에 시작점 입력 및 point도 true로 변경
        Queue<int[]> q = new LinkedList<>();
        q.add(start);
        point[start[0]][start[1]]=true;
        
        // level을 통해 몇번을 거쳐 도착했는지 확인
        int level = 0;
        
        while(!q.isEmpty()){
            level++;
            int size = q.size();
            // 동일 level별로 확인가능하도록 큐의 size만큼씩 진행
            for(int i=0;i<size;i++){
                int[] cur = q.poll();
                // 진행방향 결정
                for(int j=0;j<4;j++){
                    int nc = cur[0];
                    int nr = cur[1];
                    //해당방향으로 진행
                    while(nc >=0 && nr>=0 && nc <board.length && nr<board[0].length() && b[nc][nr]!='D'){
                        nc += dc[j];
                        nr += dr[j];
                    }
                    // 도착점에 도달한 경우 -> bfs로 구현하였기 때문에 바로 리턴가능
                    if(b[nc-dc[j]][nr-dr[j]]=='G') return level;
                    
                    // 막힌경우 이전 계산 여부 판단 후 큐에 새로 입력
                    if(!point[nc-dc[j]][nr-dr[j]]) {
                        q.add(new int[] {nc-dc[j], nr-dr[j]});
                        point[nc-dc[j]][nr-dr[j]]=true;
                    }
                }
            }
        }
        // 바로 리턴되지 않은경우 -> 도착점 도달에 실패했으므로 -1 리턴
        return answer;
    }
}