[프로그래머스 level2] 리코쳇로봇 자바 BFS 큐

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

프로그래머스

문제

* @param board 보드상황 표현. "." : 빈 공간, "R" : 출발위치 "D" : 장애물 "G" : 목적지
* @return G까지 최소 이동거리. 불가능시 -1;

이 게임은 한 번 이동할 때 상하좌우 한 방향으로 벽이나 장애물에 부딪힐 때 까지 계속 이동한다.

주어진 board를 바탕으로 R -> G까지 필요한 최소 이동거리를 구하여라. (불가능할 경우 -1)

리코쳇

접근

보드의 출발점 ~ 목적지까지의 최소거리는 BFS방식이 효율적이라고 알고 있다.
나름의 시도로 String[]으로 된 기존 데이터를 int[][]로 변환해서 시도하면 어떨까 하였으나,
이동방식에 대한 응용이 쉽지 않았다.
그리하여 폐기 후 피드백을 수용하여 처리하였음.

피드백

🔧 핵심 아이디어

1. BFS 큐를 사용해서 위치와 이동 횟수를 저장합니다.
2. 한 방향으로 움직일 때 "장애물" 또는 "경계"에 닿기 전까지 계속 이동합니다.
3. 도달한 좌표 중 방문하지 않은 위치만 큐에 넣어 다시 BFS를 계속합니다.
4. 목표 지점 'G'에 도달하면 해당까지의 이동 횟수를 반환합니다.
5. BFS가 끝날 때까지 도달하지 못하면 -1 반환.

---

📌 구현 포인트

• 미끄러질 때는 while 문으로 쭉 이동시키고, 그 직전 위치를 새 큐에 넣습니다.
• 방문 여부를 기록하는 boolean[][] visited 배열 필요.
• 처음 시작 좌표는 'R'에서 시작함.

public int solution(String[] board) {
        int rows = board.length;
        int cols = board[0].length();
        boolean[][] visited = new boolean[rows][cols];
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};

        Queue<int[]> q = new LinkedList<>();

        //출발위치 지정
        outer:
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j ++){
                if(board[i].charAt(j) == 'R'){
                    q.add(new int[]{i, j, 0}); // row, col, 이동횟수.
                    visited[i][j] = true;
                    break outer;
                }
            }
        }

        while (!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], cnt = cur[2];

            if(board[x].charAt(y) == 'G') return cnt;

            for(int d = 0; d < 4; d ++){
                int nx = x;
                int ny = y;

                //미끄러져서 끝까지 이동
                while(true){
                    int tx = nx + dx[d], ty = ny + dy[d];
                    if(tx < 0 || ty < 0 || tx >= rows || ty >= cols || board[tx].charAt(ty) == 'D') break;
                    nx = tx;
                    ny = ty;
                }

                if(!visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny, cnt +1});
                }
            }
        }

        return -1;
    }

알게된 점

1. 다중 반복문일 경우 break로 원하는 범위까지 한꺼번에 탈출하기
    -> 원하는 지점에 '변수명': 로 선언 후 break 변수명;으로 탈출
2. LinkedList에 경우 고정된 길이가 아니므로 Queue.add나 offer은 큰 차이가 없음.