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

❓문제설명

리코쳇 로봇

프로그래머스

 

---

🔍 문제해석

어떤걸 풀어야 할까?

• 시작위치에서 도착 위치까지 도달하는데에 최소 이동 횟수를 구하자
• 상하좌우로 이동 가능한데, 장애물을 만나거나 배열의 범위를 넘어가지 않으면 한방향으로 쭉 이동이 가능하고, 그게 한번의 이동횟수로 카운트 된다.
• 만약 도착지점에 도달하지못한다면 -1을 리턴한다.

---

🧐 문제 풀이

• 문제 풀이 구상

시작지점으로 부터 상하좌우로 미끄러진다는 개념을 코드화 해야한다.

상하좌우 네 방향으로 움직이는 걸 계산하되 장애물이나 배열의 끝을 만나지 않는다면 계속 한 방향으로 이동하도록 한다.

만약 장애물이나 배열의 범위를 맞닥드린다면 계산 한걸 다시 빼주고, 이동이 완료했다는 뜻이니 이동횟수를 더해준다.

근데 방문 여부는 왜 계산하는지 모르겠다. 도착지점에 도달하지 못하는 케이스가 있는걸로 보아 

방문 여부 체크를 해야할 것 같은데 왜 하는지.. 모르겠음

코드는 아래 블로그를 참조함

참조 블로그 : https://stdio-han.tistory.com/226

 

• 알고리즘 선택

최소 이동 횟수를 구하라는 지문을 보고 BFS를 선택하였다.

---

！ 제출코드

1. 방문여부 체크 배열과, 방향계산을 위한 배열, 답을 담을 변수를 static으로 선언한다. 
2. 시작지점을 구한다.
3. 움직일 수 있는 정점들의 위치와 이동 횟수를 담아 queue에 넣고, queue가 텅 빌 때까지 이동을 계속한다. 만약 queue가 없을 때 까지 답이 계산되지 않는다면 -1을 리턴한다.
4. 도착지점에 도달하면 횟수를 answer에 담고 리턴한다.
5. 그게 아니라면 이동을 시작한다.
6. 현재 위치가 boar의 범위 안이고, 장애물도 만나지 않는다면 같은 방향으로 계속 계산한다.
7. 그렇지 않은 경우에는 다시 -계산을 해주어 다시 뒤로 돌아간다.
8. 만약 그렇게 해서 도달한 위치가 이미 방문한 적이 있거나 처음 이동하기 시작한 위치와 같다면 거기서 멈추고 다음 방향의 계산으로 넘어간다.
9. 처음 방문한 거라면 방문 체크를 하고
10. 이동횟수를 더한다음 다음 정점으로 넘어간다.

import java.util.*;

class Solution {
     // (1)
    static int [][] visitBoard;
    static int [] dy = {0,0,1,-1};
    static int [] dx = {1,-1,0,-0};
    static int answer = -1;
    
    public static int solution(String[] board) {
    
        int m = board.length;
        int n = board[0].length();
        visitBoard = new int[m][n];
        int [] start = new int[]{0,0};
        Queue<int[]> queue = new LinkedList<>();
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            
                 // (2)
                if('R' == board[i].charAt(j)) {
                    start = new int[]{i,j};
                    visitBoard[i][j] = 1;
                }
            }
        }
        
        // y, x, count
        queue.offer(new int[]{start[0],start[1],0});
        
        // (3)
        while (!queue.isEmpty()) {
            
            int[] point = queue.poll();
            int y = point[0];
            int x = point[1];
            int count = point[2];
            
            // (4)도착지점이면 answer에 값 대입
            if(board[y].charAt(x) == 'G') {
            
                answer = count;
                return answer;
            }
            
            // (5) 상하좌우 방향 이동 해보기 
            for (int i = 0; i < 4; i++) {
            
               int nx = x;
               int ny = y;
               
               // (6)
               while (ny > -1 && ny < board.length 
               && nx > -1 && nx < board[0].length()
               && board[ny].charAt(nx) != 'D') {
               
                   ny += dy[i];
                   nx += dx[i];
               }
               
               // (7)
               ny -= dy[i];
               nx -= dx[i];
               
               // (8)방문한 적이 있거나 처음 시작한 위치와 같은 위치면 continue
               if(visitBoard[ny][nx] == 1 || y == ny && x == nx) continue;
               
               // (9)처음 방문한 거라면 체크하고
               visitBoard[ny][nx] = 1;
               
               // (10)다음 레벨로 넘어감
               queue.offer(new int[]{ny,nx ,count+1});
            }
        }
        return answer;
    }
}