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

오랜만에 푼 BFS 문제!

한참 알고리즘 풀 때 DFS, BFS는

거의 자동으로 나왔는데

지금은 많이 생각하고, 고민하고 풀었다.

 

알고리즘은 정말 연습만이 답인듯

 

 

---

문제

 

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

프로그래머스

 

 

---

설계

 

알고리즘 설계 [접근 방법] : BFS

가장 빠른 길 찾기 문제는 역시 BFS다.

이 문제가 일반적인 BFS문제와 다른 점은 한 칸 이동을 하나로 계산하는 것이 아니라,

벽을 만나거나 장애물을 만나서 멈추게 되는 상황까지 이동하고 그 이동을 하나로 계산하는 것이다.

때문에 3중 반복문을 만들어 시간초과가 발생하지 않을까 걱정했는데, 방법이 이것밖에 떠오르지 않았다.

다행히 시간초과는 발생하지 않았다!

 

풀이 과정

1.

가장 먼저 2차원 배열을 생성하고, 매개변수로 들어온 값을 2차원 배열에 맞에 저장한다.

그리고 시작점인 R이 있는 시작좌표를 찾는다.

 

2.

사방탐색을 하기 위해 배열 r, c를 초기화하고, 방문체크배열을 위한 2차원 배열을 생성한다.

 

3.

BFS 메서드에서는 큐를 생성하고, 시작좌표를 방문체크 후 큐에 넣는다.

 

4.

큐에서 현재 좌표를 뽑고, 만약 현재 좌표가 목적지인 'G'라면 answer를 갱신하고 return한다.

 

5.

현재 좌표에서 사방탐색을 하기 위해 dr, dc를 생성한다. 그리고 현재 방향으로 누적하여 이동한다.

이동했을 때 좌표가 배열을 넘어서거나, 장애물 'D'라면 이동을 중지한다. (반복문을 중지한다)

또한 이미 방문한 좌표라면 다음 좌표로 이동한다.

 

6.

- 장애물을 만나 멈춘 경우

만약 이동한 dr, dc 기준으로 한 번 더 이동한 좌표의 값이 'D'라면, 이동을 멈춘다.

dr, dc 좌표를 방문체크를 하고 값을 큐에 넣는다.

 

- 벽을 만나 멈춘 경우

이동한 dr, dc 기준으로 한 번 더 이동한 좌표의 값이 -1이거나 n 또는 m이고, 좌표의 값이 'D'가 아닐 경우 이동을 멈춘다.

dr, dc 좌표를 방문체크를 하고 값을 큐에 넣는다

 

7.

만약 큐에 값이 모두 없어 반복문이 종료되었는데, answer이 갱신되지 않은경우 목표지점까지 도달할 수 없는 경우다.

 

8.

answer를 출력한다.

 

 

---

코드

import java.util.*;

class Solution {
    
    static int n, m, answer;
    static int[] r, c;
    static char[][] map;
    static boolean[][] isvisited;
    
    
    public int solution(String[] board) {
        
        int sr = 0;
        int sc = 0;
        
        map = new char[board.length][board[0].length()];
        for(int i=0; i<board.length; i++){
            map[i] = board[i].toCharArray();
        }
        
        n = map.length;
        m = map[0].length;
        
        //시작 좌표 찾기
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j]=='R') {
                    sr = i; sc = j; 
                    break;
                }
            }
        }
        
        r = new int[] {-1, 0, 1, 0};
        c = new int[] {0, 1, 0, -1};
        isvisited = new boolean[n][m];
        
        answer = -1;
        BFS(sr, sc);

        return answer;
    }
    
    public static void BFS(int sr, int sc){
        Queue<int[]> queue = new LinkedList();
        
        isvisited[sr][sc] = true;
        queue.add(new int[] {sr, sc, 0});
        
        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            
            int cr = curr[0];
            int cc = curr[1];
            int depth = curr[2];
            
            if(map[cr][cc]=='G') {
                answer = depth;
                return;
            }
            
            //4방향 탐색
            for(int k=0; k<4; k++){
                int dr = cr;
                int dc = cc;
               
                while(true) {
                    
                    dr+=r[k];
                    dc+=c[k];
   
                    if(!(0<=dr && dr<n && 0<=dc && dc<m)) break;
                    if(map[dr][dc]=='D') break;
                    if(isvisited[dr][dc]) continue;
                    
                    if(0<=dr+r[k] && dr+r[k]<n && 0<=dc+c[k] && dc+c[k]<m 
                            && map[dr+r[k]][dc+c[k]]=='D'){
                        isvisited[dr][dc]=true;
                        queue.add(new int[] {dr, dc, depth+1});
                        break;     
                    }
                    if((dr+r[k]==-1 || dr+r[k]==n || dc+c[k]==-1 || dc+c[k]==m)
                           && map[dr][dc]!='D') {
                        isvisited[dr][dc]=true;
                        queue.add(new int[] {dr, dc, depth+1});
                        break; 
                    }
                }
            }
        }
    }
}

 

 

(❁´◡`❁)

끝!