Programmers - 리코쳇 로봇 with JAVA

 

 

로직

1. 미끄러져 방문한 노드는 방문처리해서 다시 방문하지 않아도 된다.

2. 시작점, 목표점 또한 방문 가능한 노드임을 인지한다.

 

 

 

 

코드

import java.util.*;
class Solution {
    public int solution(String[] board) {
        int answer = -1;
        int x_len = board.length;
        int y_len = board[0].length();
        int[] start = new int[2];
        int[] end = new int[2];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        for(int i=0; i<x_len; i++){
            for(int j=0; j<y_len; j++){
                if(board[i].charAt(j) == 'R'){
                    start[0] = i;
                    start[1] = j;
                }
                if(board[i].charAt(j) == 'G'){
                    end[0] = i;
                    end[1] = j;
                }
            }
        }
        PriorityQueue<List<Integer>> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        queue.add(Arrays.asList(0, start[0], start[1]));
        boolean[][] visited = new boolean[x_len][y_len];
        while(queue.size() > 0){
            List<Integer> now = queue.poll();
            int cost = now.get(0);
            int x = now.get(1);
            int y = now.get(2);
            if(visited[x][y]){
                continue;
            }
            visited[x][y] = true;
            if(board[x].charAt(y) == 'G'){
                answer = cost;
                break;
            }
            for(int i=0; i<4; i++){
                int next_x = x + dx[i];
                int next_y = y + dy[i];
                if(next_x < 0|next_x >= x_len|next_y < 0|next_y >= y_len){
                    continue;
                }
                if(board[next_x].charAt(next_y) == '.' | board[next_x].charAt(next_y) == 'R'
                | board[next_x].charAt(next_y) == 'G'){
                    if(i == 0){
                        while(board[next_x].charAt(next_y) != 'D'){
                            next_x -= 1;
                            if(next_x < 0){
                                next_x = 0;
                                break;
                            }
                        }
                        if(board[next_x].charAt(next_y) == 'D'){
                            next_x += 1;
                        }
                    }
                    if(i == 1){
                        while(board[next_x].charAt(next_y) != 'D'){
                            next_y -= 1;
                            if(next_y < 0){
                                next_y = 0;
                                break;
                            }
                        }
                        if(board[next_x].charAt(next_y) == 'D'){
                            next_y += 1;
                        }
                    }
                    if(i == 2){
                        while(board[next_x].charAt(next_y) != 'D'){
                            next_x += 1;
                            if(next_x >= x_len){
                                next_x = x_len-1;
                                break;
                            }
                        }
                        if(board[next_x].charAt(next_y) == 'D'){
                            next_x -= 1;
                        }
                    }
                    if(i == 3){
                        while(board[next_x].charAt(next_y) != 'D'){
                            next_y += 1;
                            if(next_y >= y_len){
                                next_y = y_len-1;
                                break;
                            }
                        }
                        if(board[next_x].charAt(next_y) == 'D'){
                            next_y -= 1;
                        }
                    }
                    queue.add(Arrays.asList(cost+1, next_x, next_y));   
                }
            }
        }
        return answer;
    }
}

 

 

이동을 재귀로 구현한 코드

import java.util.*;
class Solution {
    public int solution(String[] board) {
        int answer = -1;
        int n = board.length;
        int m = board[0].length();
        int[] start = new int[2];
        int[] end = new int[2];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        for(int x=0; x<n; x++){
            for(int y=0; y<m; y++){
                if(board[x].charAt(y) == 'R'){
                    start[0] = x;
                    start[1] = y;
                }
                if(board[x].charAt(y) == 'G'){
                    end[0] = x;
                    end[1] = y;
                }
            }
        }
        PriorityQueue<List<Integer>> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        boolean[][] visited = new boolean[n][m];
        queue.add(Arrays.asList(0, start[0], start[1]));
        while(queue.size() > 0){
            List<Integer> now = queue.poll();
            int cost = now.get(0);
            int x = now.get(1);
            int y = now.get(2);
            if(visited[x][y]){
                continue;
            }
            if(x == end[0] && y == end[1]){
                return cost;
            }
            visited[x][y] = true;
            for(int i=0; i<4; i++){
                List<Integer> next = move(x, y, board, i);
                int next_x = next.get(0);
                int next_y = next.get(1);
                if(visited[next_x][next_y]){
                    continue;
                }
                queue.add(Arrays.asList(cost+1, next_x, next_y));
            }
        }
        return answer;
    }
    public static List<Integer> move(int x, int y, String[] board, int i){
        if(i == 0){
            if(x < 0){
                return Arrays.asList(x+1, y);
            }
            if(board[x].charAt(y) == 'D'){
                return Arrays.asList(x+1, y);
            }
            return move(x-1, y, board, i);
        }
        else if(i == 1){
            if(y < 0){
                return Arrays.asList(x, y+1);
            }
            if(board[x].charAt(y) == 'D'){
                return Arrays.asList(x, y+1);
            }
            return move(x, y-1, board, i);
        }
        else if(i == 2){
            if(x >= board.length){
                return Arrays.asList(x-1, y);
            }
            if(board[x].charAt(y) == 'D'){
                return Arrays.asList(x-1, y);
            }
            return move(x+1, y, board, i);
        }
        else{
            if(y >= board[0].length()){
                return Arrays.asList(x, y-1);
            }
            if(board[x].charAt(y) == 'D'){
                return Arrays.asList(x, y-1);
            }
            return move(x, y+1, board, i);
        }
    }
}