리코쳇 로봇 [자바]

 

🧫 문제 분석

✔️ 출처

리코쳇 로봇 level 2

📖 문제

 

BFS 문제로 다른점은 한방향으로 쭉 가야한다는 것과

D라는 장애물이나 가장자리 즉, 배열의 범위를 넘어서는 곳을 만나면 멈춘다는 것이다. 

 

장애물을 만나거나, 가장자리 (배열 범위)를 넘어선 곳을 만날때 멈춘 자리가 G(목표지점) 인지 확인하면 되는 단순한 문제이다.

 

---

🔅 문제 풀이

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    boolean[][][] visited;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int answer = 0;

    class Token {
        int y;
        int x;
        int step;

        public Token(int y, int x, int step) {
            this.y = y;
            this.x = x;
            this.step = step;
        }

        @Override
        public String toString() {
            return "Token{" +
                    "y=" + y +
                    ", x=" + x +
                    ", step=" + step +
                    '}';
        }
    }

    public int solution(String[] board) {
        visited = new boolean[4][board.length][board[0].length()];
        Token robot = getRobotInfo(board);

        // 로봇 시작 위치는 방문 처리
        for (int i = 0; i < 4; i++) {
            visited[i][robot.y][robot.x] = true;
        }

        findGoalPointDistance(robot, board);

        return answer == 0 ? -1 : answer;
    }


    private void findGoalPointDistance(Token robot, String[] board) {
        Queue<Token> q = new LinkedList<>();
        q.add(robot);

        while(!q.isEmpty()) {
            Token currentRB = q.poll();

            for (int i = 0; i < 4; i++) {
                int tmp_y = currentRB.y;
                int tmp_x = currentRB.x;

                // 한 방향으로 쭉 이동시키기
                while (true) {
                    tmp_y += dy[i];
                    tmp_x += dx[i];

                    // 벽을 만나거나, 이미 방문한 곳이면 멈춤
                    if (tmp_y == -1 || tmp_y == board.length
                            || tmp_x == -1|| tmp_x == board[0].length()) {
                        tmp_y -= dy[i];
                        tmp_x -= dx[i];

                        if (board[tmp_y].charAt(tmp_x) == 'G') {
                            answer = currentRB.step + 1;
                            return;
                        }

                        if (!visited[i][tmp_y][tmp_x]) {
                            q.add(new Token(tmp_y, tmp_x, currentRB.step + 1));
                            visited[i][tmp_y][tmp_x] = true;
                        }

                        break;
                    }

                    if (visited[i][tmp_y][tmp_x]) break;

                    // D인 장애물을 만났을 경우
                    if (board[tmp_y].charAt(tmp_x) == 'D') {
                        tmp_y -= dy[i];
                        tmp_x -= dx[i];

                        // 목표 지점에 도달하면 그것이 이동 최소값
                        // 큐를 이용한 BFS 활용 탐색이라 먼저 발견된 것이 가장 작은 값
                        // 장애물에 부딪혀서 현재 위치가 목표지점인 경우 값 저장후 리턴
                        if (board[tmp_y].charAt(tmp_x) == 'G') {
                            answer = currentRB.step + 1;
                            return;
                        }

                        if (!visited[i][tmp_y][tmp_x]) {
                            // 장애물 전 위치를 큐에 저장하고 방문 체크
                            q.add(new Token(tmp_y, tmp_x, currentRB.step + 1));
                            visited[i][tmp_y][tmp_x] = true;
                        }
                        break;
                    }
                }
            }
        }
    }

    private Token getRobotInfo(String[] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length(); j++) {
                if (board[i].charAt(j) == 'R') {
                    return new Token(i, j, 0);
                }
            }
        }
        return null;
    }
}

 

여기서 visited를 3중 배열로 했는데  처음 풀이때 2중배열을 하면 틀렸었다. 

왜 그런지 visited를 2중배열로 하고 리팩토링해봤는데

if (visited[tmp_y][tmp_x]) break;

// D인 장애물을 만났을 경우
if (board[tmp_y].charAt(tmp_x) == 'D') {

이 부분이 문제였다.

진행 방향으로 가는 도중에 해당 지점이 이미 로봇이 방문했던 곳이라고 break를 해버려 진행하지 못하고 종료되는 경우때문에 틀렸던 것이였다.  (테스트 8번)

 

해결 방법

단순히 break를 continue로 바꿔 진행 방향으로 계속 가게 해주면 된다. 

if (visited[tmp_y][tmp_x]) continue;

 

 

 

🔅 리팩토링

import java.util.*;

class Solution {
    boolean[][] visited;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int answer = 0;

    class Token {
        int y;
        int x;
        int step;

        public Token(int y, int x, int step) {
            this.y = y;
            this.x = x;
            this.step = step;
        }
    }

    public int solution(String[] board) {
        visited = new boolean[board.length][board[0].length()];
        Token robot = getRobotInfo(board);

        // 로봇 시작 위치는 방문 처리

        visited[robot.y][robot.x] = true;
        findGoalPointDistance(robot, board);
        
        return answer == 0 ? -1 : answer;
    }


    private void findGoalPointDistance(Token robot, String[] board) {
        Queue<Token> q = new LinkedList<>();
        q.add(robot);

        while(!q.isEmpty()) {
            Token currentRB = q.poll();

            for (int i = 0; i < 4; i++) {
                int tmp_y = currentRB.y;
                int tmp_x = currentRB.x;

                // 한 방향으로 쭉 이동시키기
                while (true) {
                    tmp_y += dy[i];
                    tmp_x += dx[i];

                    // 벽을 만나거나, D인 장애물을 만나면 멈춤
                    if (tmp_y == -1 || tmp_y == board.length
                            || tmp_x == -1|| tmp_x == board[0].length()
                            || board[tmp_y].charAt(tmp_x) == 'D') {
                        tmp_y -= dy[i];
                        tmp_x -= dx[i];
                        break;
                    }

                }

                if (visited[tmp_y][tmp_x]) continue;
                if (checkCurrentPoint(board, tmp_y, tmp_x, currentRB, i, q)) return;
            }
        }
    }

    private boolean checkCurrentPoint(String[] board, int tmp_y, int tmp_x, Token currentRB, int i, Queue<Token> q) {
        if (board[tmp_y].charAt(tmp_x) == 'G') {
            answer = currentRB.step + 1;
            return true;
        }

        q.add(new Token(tmp_y, tmp_x, currentRB.step + 1));
        visited[tmp_y][tmp_x] = true;
        return false;
    }

    private Token getRobotInfo(String[] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length(); j++) {
                if (board[i].charAt(j) == 'R') {
                    return new Token(i, j, 0);
                }
            }
        }
        return null;
    }
}

 

❗ 오답노트 / 필요한 지식

1. 예전에 벽 부수고 가는 방법, 넘어가는 방법등 여러가지 방법이 있을 경우 BFS에서 visited를 경우에 따라 나누는 것이 생각나서 3중 배열로 했었는데 생각해보니까 이 문제의 경우는 어짜피 4방향으로 가고, 가는 길이 비슷하기에 상관없었다.