리코쳇 로봇

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

프로그래머스

 

로봇은 장애물이나 벽에 부딪힐때 까지 한 방향으로만 움직이며,

 

로봇이 멈추는 경우는

1. 벽을 만났거나

2. 장애물을 만났을 경우

이다.

 

로봇이 멈춘 곳이 목표 지점인 경우, 몇번 움직였는지를 체크해야 한다.

 

DFS로 풀었는데.. 풀고 보니 BFS로 풀었어도 되었을것 같다.

 

class Solution {
    
    // 로봇이 움직일 수 있는 방향. (x, y) 좌표로 구성됨
    private int[][] moving = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    // 보드 판의 가로 크기
    private int width;
    // 보드 판의 세로 크기
    private int height;
    
    // 목표지점 찾았는지 여부
    private boolean find = false;
    // 몇번 움직였는지
    private int answer = Integer.MAX_VALUE;
    
    public int solution(String[] board) {
        
        width = board[0].length();
        height = board.length;
        
        // 목표 지점 좌표
        int[] goal = new int[2];
        // 시작 지점 좌표
        int[] init = new int[2];
        
        // 보드판을 int[][] 로 변환했다.
        // 여러 케이스 중 같은 지점을 방문한 경우
        // 이전에 움직였던 횟수와 비교해서 탐색 횟수를 조금이라도 줄일 목적으로
        // 해당 지점에 방문했을 때의 움직인 횟수를 캐시한다.
        // 횟수는 1 이상의 값이므로, 장애물은 음수값으로 저장해두었다.
        // 유의할점은 y, x 좌표이다. ㅋㅋ
        int[][] cache = new int[height][width];
        
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                
                char c = board[i].charAt(j);
                
                if (c == 'R') {
                    init[0] = j;
                    init[1] = i;
                } else if (c == 'G') {
                    goal[0] = j;
                    goal[1] = i;
                }
                
                if (c == 'D') {
                	// 장애물이 있는 곳엔 음수값을 둔다.
                    cache[i][j] = Integer.MIN_VALUE;
                } else {
                	// 최대값으로 초기화한다.
                    cache[i][j] = Integer.MAX_VALUE;
                }
                
            }
        }
        
        // 시작 지점부터 동서남북 방향으로 움직인다.
        move(cache, goal, 0, init, 1);
        move(cache, goal, 1, init, 1);
        move(cache, goal, 2, init, 1);
        move(cache, goal, 3, init, 1);
        
        // 답을 찾았다면 횟수를, 못찾았다면 -1 리턴
        return find ? answer : -1;
    }
    
    /**
    * direction : 움직일 방향
    * curr : 현재의 (x, y) 좌표
    * cnt : 움직인 횟수
    */
    void move(int[][] board, int[] goal, int direction, int[] curr, int cnt) {
        
        // System.out.printf("[%d회차] (%d, %d)\n", cnt, curr[0], curr[1]);
        
        // direction으로 움직였을 때의 다음 좌표이다.
        int[] next = next(curr, direction);
        
        // 다음 좌표로 이동할 수 있는지 체크
        if (moveable(board, direction, next)) {
        	// 다음 좌표로 이동 가능하다면 이동한다.
            // System.out.printf("-> (%d, %d)\n", next[0], next[1]);
            move(board, goal, direction, next, cnt);
            return;
        }
        
        // 다음 좌표로 이동할 수 없다면 무언가에 부딪힌 상황이다.
        int prev = board[curr[1]][curr[0]];
        // 이전에 저장된 움직인 횟수와 비교해서 종료 여부를 판별한다.
        if (prev < cnt) return;
        
        // 멈춘 곳이 목표지점인지 체크한다.
        if (goal[0] == curr[0] && goal[1] == curr[1]) {
            find = true;
            answer = Math.min(answer, cnt);
            return;
        }
        
        // 멈춘 곳에 움직인 횟수를 저장한다.
        // 이전에 저장한 값보다 큰 경우는 위의 91라인에서 튕겨났으므로 신경쓰지 않는다.
        board[curr[1]][curr[0]] = cnt;
        
        int incr = cnt + 1;
        if (direction < 2) {
        	// 동 또는 서 로 움직여서 해당 좌표로 온 경우 서 또는 동 으로는 움직일 필요가 없다.
            int[] toNorth = next(curr, 2);
            if (moveable(board, 2, toNorth)) {
                move(board, goal, 2, toNorth, incr);
            }
            
            int[] toSouth = next(curr, 3);
            if (moveable(board, 3, toSouth)) {
                move(board, goal, 3, toSouth, incr);
            }
            
        } else {
        	// 북 또는 남 으로 움직여서 해당 좌표로 온 경우 남 또는 북 으로는 움직일 필요가 없다.
            int[] toEast = next(curr, 0);
            if (moveable(board, 0, toEast)) {
                move(board, goal, 0, toEast, incr);
            }
            
            int[] toWest = next(curr, 1);
            if (moveable(board, 1, toWest)) {
                move(board, goal, 1, toWest, incr);
            }
            
        }
        
    }
    
    boolean between(int num, int min, int max) {
        return num >= min && num <= max;
    }
    
    int[] next(int[] curr, int direction) {
        return new int[] { curr[0] + moving[direction][0], curr[1] + moving[direction][1] };
    }
    
    boolean moveable(int[][] board, int direction, int[] next) {
        // 벽을 넘었는지,
        boolean inX = between(next[0], 0, width - 1);
        boolean inY = between(next[1], 0, height - 1);
        
        if (inX && inY) {
        	// 장애물은 아닌지,
            int val = board[next[1]][next[0]];
            
            return val > 0;
        }
        
        return false;
        
    }
    
}