[프로그래머스/Level2] 리코쳇 로봇 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• BFS

 

로봇이 있는 위치부터 BFS를 진행한다.

 

- 큐에 로봇 위치 rx,ry와 이동 거리를 저장한다.- 만약 현재 위치가 목적지인 경우, 정답을 여태까지의 이동 거리로 설정하고 while문을 종료한다.- 목적지가 아니라면, 다음 이동할 지점을 찾는다.   - 현재 지점에서 4방향 탐색을 한다. 이 때 한 방향을 정해서 해당 방향으로 최대한 끝까지 탐색을 진행한다. (while문 사용)   - 진행하다가 격자 범위를 벗어나거나 장애물을 마주친다면, 현재 이동 좌표의 직전 좌표를 사용하고 현재 while문을 나온다.

 

- 이제 다음 이동할 지점을 방문한 적 없다면, 해당 지점에서 탐색을 시작한다. (큐에 해당 위치 rx, ry와 이동거리+1 저장)

 

 

 

💥 유의사항

한 방향을 정해서 그 방향으로 끝까지(격자 범위를 벗어나거나, 장애물에 닿기 전까지) 진행하는 것을 잊어서는 안 된다..

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int n, m;
    static char[][] map;
    static boolean[][] visited;    
    static int rx = 0, ry = 0;
    
    public int solution(String[] board) {
        n = board.length;
        m = board[0].length();
        
        map = new char[n][m];
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                map[i][j] = board[i].charAt(j);
                
                if(map[i][j] == 'R') {
                    rx = i;
                    ry = j;
                }
            }
        }
        
        visited = new boolean[n][m];        
        return bfs();
    }
    
    private static int bfs() {       
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {rx, ry, 0});
        
        int answer = -1;    // 도착 지점에 도착 못 하면 -1 반환
        visited[rx][ry] = true; 
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            if(map[now[0]][now[1]] == 'G') {    // 💥 현재 지점이 도착 지점인 경우
                answer = now[2];
                break;
            }
            
            for(int d = 0 ; d < 4 ; d++) {  // 4방향 탐색
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                while(true) {   // 💥 해당 방향으로 최대한 끝까지 탐색
                    if(inRange(nx, ny) && map[nx][ny] != 'D') {
                        nx += dx[d];
                        ny += dy[d];
                    }
                    else {  // 격자 범위 벗어나거나 장애물이 있는 지점인 경우, 직전 좌표 사용
                        nx -= dx[d];
                        ny -= dy[d];
                        break;
                    }  
                }
                
                if(!visited[nx][ny]) {  // 해당 지점 방문한 적 없다면, 해당 지점에서 탐색
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny, now[2] +1});
                }
            }
        }
                
        return answer;
    }
    
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
}

 

 

 

➕ 다른 풀이 방식

우선순위 큐를 사용한 방식 (이걸 뭐라고 하더라..)

(Java) 프로그래머스 - 리코쳇 로봇

 

---

💦 어려웠던 점

- 해당 방향으로 최대한 끝까지 탐색하라는 문구를 우짜지 하다가 틀렸답,,,

 

 

 

🧐 새로 알게 된 내용

- 한 방향을 정해서 끝까지 탐색하게 하는 방법을 깨달았다! (while문 위치,,,, ) 그리고 이동할 수 없으면 어떻게 처리해야 하는지도 (51-61번째 줄)

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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