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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 리코쳇 로봇

 

문제 접근

BFS 문제!

 

중요 포인트

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

 

init 데이터 설명 

 

arx, ary: 방향 

row: 행 

col: 열

map: 문자열 board를 2차원 배열로 다시 정리 

start_x, start_y: 리코쳇 로봇의 시작 좌표 

end_x, end_y: 리코쳇 로봇의 목표 좌표 

 

초기화 설명 

 

2차원 배열로 옮기는 작업 

 

cur == 'R'  start_x, start_y: 리코쳇 로봇의 시작 좌표 

cur == 'G  end_x, end_y: 리코쳇 로봇의 목표 좌표 

 

cur == 'D' 벽 map에 -1 기록

cur != 'D' map에 Integer.MAX_VALUE;

static int [] arx = {-1,1,0,0};
static int [] ary = {0,0,-1,1};

static int row; // 행
static int col; // 열 
static int [][] map;
static int start_x, start_y, end_x, end_y;

public int solution(String[] board){
    row = board.length;
    col = board[0].length();
    map = new int [row][col];
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            char cur = board[i].charAt(j);

            if(cur == 'R'){
                start_x = i;
                start_y = j;
            }

            if(cur == 'G'){
                end_x = i;
                end_y = j;
            }

            if(cur == 'D'){
                map[i][j] = -1;
            }
            else map[i][j] = Integer.MAX_VALUE;
        }
    }

 

validaiton (검증 로직) for  Array Index Out Of Bounds Exception

 

행, 열 크기 안의 움직임인지 check 용도

public static boolean validation(int nx, int ny){
    if(0 <= nx && 0 <= ny && nx < row && ny < col) return true;
    return false;
}

 

BFS() 핵심 로직 

 

리코쳇 로봇의 시작 좌표를 0으로 기록: map[start_x][start_y] = 0;

 

2차원 배열이니까 Queue도 알맞게 초기화

 

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

0: x좌표 1: y좌표

 

큐에 시작 좌표를 넣는다. 

 

while문 시작

 

큐에서 하나 꺼내기 : int [] cur = q.poll(); 

cur_x = cur[0] = x좌표

cur_y = cur[1] = y좌표

 

for문 시작 

for(int i = 0; i < 4; i++) 

arx{-1,1,0,0} ary{0,0,-1,1}  4가지 방향  

 

현재의 좌표에서 상,하,좌,우 방향을 정하고 장애물 map[x][y] = -1 or 맨 끝에 부딪힐 때까지 이동

 

만약 이미 현재의 좌표가 해당 방향에서 가장 끝이면 다음 좌표인 nx,ny 는 그대로다 의미 없으니 continue

만약 다음 좌표인 nx,ny가 다른 방법으로 더 최단거리로 방문 했다면 의미 없으니 continue

 

2가지 필터에서 살아남았다면 

map에 현재 map[cur_x][cur_y]에서 1번 움직인 거리를 기록 , 큐에 넣어주기

 

2가지 필터에서 살아남았다면 그 시점 기준 해당 좌표는 최단거리로 방문한 것이다. 

public static void BFS(){
    map[start_x][start_y] = 0;

    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{start_x, start_y});
    while(!q.isEmpty()){
        int [] cur = q.poll();
        int cur_x = cur[0];
        int cur_y = cur[1];
        for(int i = 0; i < 4; i++){
            int nx = cur_x + arx[i];
            int ny = cur_y + ary[i];
            while(validation(nx, ny) && map[nx][ny]!= -1){
                nx += arx[i];
                ny += ary[i];
            }
            nx -= arx[i];
            ny -= ary[i];
            // 그대로
            if(nx == cur_x && ny == cur_y) continue;
            // 최단경로가 아닌 경우 
            if(map[nx][ny] <= map[cur_x][cur_y] + 1) continue;

            map[nx][ny] = map[cur_x][cur_y] + 1;
            q.add(new int[]{nx,ny});
        }
    }
}

 

return 로직 (정답 반환 로직)

 

BFS() 로직이 끝나고 나서 만약 map[end_x][end_y]가  Integer.MAX_VALUE이라면 어떠한 방법으로도 목표 좌표로 가지 못한다는 뜻 그래서 return -1 

 

아니라면  목표 좌표의 최단거리를 return 

BFS();
if(map[end_x][end_y] == Integer.MAX_VALUE) return -1;

return map[end_x][end_y];

 

전체 코드

import java.util.*;
class Solution {
    
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    
    static int row; // 행
    static int col; // 열 
    static int [][] map;
    static int start_x, start_y, end_x, end_y;
    public int solution(String[] board){
        row = board.length;
        col = board[0].length();
        map = new int [row][col];
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                char cur = board[i].charAt(j);
                
                if(cur == 'R'){
                    start_x = i;
                    start_y = j;
                }
                
                if(cur == 'G'){
                    end_x = i;
                    end_y = j;
                }
                
                if(cur == 'D'){
                    map[i][j] = -1;
                }
                else map[i][j] = Integer.MAX_VALUE;
            }
        }
        BFS();
        if(map[end_x][end_y] == Integer.MAX_VALUE) return -1;
            
        return map[end_x][end_y];
    }
    public static void BFS(){
        map[start_x][start_y] = 0;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start_x, start_y});
        while(!q.isEmpty()){
            int [] cur = q.poll();
            int cur_x = cur[0];
            int cur_y = cur[1];
            for(int i = 0; i < 4; i++){
                int nx = cur_x + arx[i];
                int ny = cur_y + ary[i];
                while(validation(nx, ny) && map[nx][ny]!= -1){
                    nx += arx[i];
                    ny += ary[i];
                }
                nx -= arx[i];
                ny -= ary[i];
                // 그대로
                if(nx == cur_x && ny == cur_y) continue;
                // 최단경로가 아닌 경우 
                if(map[nx][ny] <= map[cur_x][cur_y] + 1) continue;
                
                map[nx][ny] = map[cur_x][cur_y] + 1;
                q.add(new int[]{nx,ny});
            }
        }
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < row && ny < col) return true;
        return false;
    } 
}

 

감사합니다 !