[프로그래머스] 리코쳇 로봇 (자바)

https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=java 

프로그래머스

 

 

문제 

주어진 보드에서 로봇이 R 에서 시작해서 G 지점으로 가는데 까지의 최소 움직임을 구하는 횟수

 

단 로봇이 움직일 때는 한 칸이 아닌, 미끄러져서 해당 방향의 보드 끝까지 나아간다는 점이다. 

---

풀이

최소를 구하는 문제이니 BFS 사용해서 해결할 수 있다. 

 

흔히 사용하는 출발점에서 목표점까지 가는 최소거리 문제에서 로봇의 움직임만 주의해주면 된다. 

로봇은 끝까지 가기때문에 상하좌우 4가지 경우를 선택해서 장애물이 나오거나 보드 지점 끝까지 가면 된다. 

 

visited 항목은 로봇이 미끄러져서 도달한 지점 기준으로 작성하면 된다. 

 

 

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

class Solution {
    public int solution(String[] board) {
        int answer = 0;
        String[][] map = new String[board.length][board[0].length()];
        boolean[][] visited = new boolean[board.length][board[0].length()];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int[] start = new int[2];
        
        for(int i = 0; i<board.length; i++) {
            String[] tmp = board[i].split("");
            
            for(int j = 0; j<tmp.length; j++) {
                map[i][j] = tmp[j];
                
                if (tmp[j].equals("R")) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        
    	// BFS 시작점
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;
        
        while(!queue.isEmpty()) {
            int[] q = queue.poll();
            int y = q[0];
            int x = q[1];
            int cnt = q[2];

			// 이동
            for(int i = 0; i<4; i++) {
                int nx = x;
                int ny = y;
                
                // 끝까지 이동 ( 보드를 넘어가거나, 장애물에 부딪힐 때 stop )
                while(true) {
                    if ( ny < 0 || ny >= map.length || nx < 0 || nx >= map[0].length ) {
                        break;
                    }
                    
                    if (map[ny][nx].equals("D")) {
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                    
                    nx += dx[i];
                    ny += dy[i];
                }
                
                // 보드를 넘어갈 경우, 방향에 따라 위치 재조정
                if ( ny < 0 || ny >= map.length || nx < 0 || nx >= map[0].length ) {
                    if (i == 0 ) {
                        nx = map[0].length - 1;
                    } else if (i == 1) {
                        nx = 0;
                    } else if (i == 2) {
                        ny = map.length - 1;
                    } else {
                        ny = 0;
                    }
                }
                
                if (map[ny][nx].equals("G")) {
                    return cnt + 1;
                }
                
                if (!visited[ny][nx]) {
                    queue.add(new int[]{ny, nx, cnt + 1});
                    visited[ny][nx] = true;
                }
            }
        }
        
        return -1;
    }
}