[Programmers] 리코쳇 로봇 / ⭕

프로그래머스

 

1. 제출 코드 (41분 25초 / BFS)

import java.util.*;
class Solution {
    static class Pos {
        int x, y, dist;
        public Pos(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Pos robot, target;
    static boolean[][] visited;
    static ArrayList<Character>[] map;
    
    public int solution(String[] board) {
        int answer = 0;
        // BFS
        map = new ArrayList[board.length];
        // 방문 배열
        visited = new boolean[board.length][board[0].length()];
        
        for(int i = 0; i < board.length; i++) {
            map[i] = new ArrayList<Character>();
            for(int j = 0; j < board[i].length(); j++) {
                char curr = board[i].charAt(j);
                // 로봇 위치 저장
                if(curr == 'R') {
                    robot = new Pos(i, j, 0);
                    visited[i][j] = true;
                } else if(curr == 'G') {
                	// 목표 지점 저장 
                    target = new Pos(i, j, 0);
                }
                map[i].add(curr);
            }
        }
        answer = bfs();
        return answer;
    }
    static int bfs() {
        ArrayDeque<Pos> q = new ArrayDeque<>();
        q.add(robot);
        
        while(!q.isEmpty()) {
            Pos t = q.poll();
            // 목표 지점에 닿을 경우
            if(t.x == target.x && t.y == target.y) {
                return t.dist;
            }
            
            for(int i = 0; i < 4; i++) {
                int dist = 1;
                int nx;
                int ny;
                // 미끄러지면서 벽의 끝이나 장애물에 닿아야 하므로
                while(true) {
                    nx = t.x + dx[i] * dist;
                    ny = t.y + dy[i] * dist;
                    
                    if(nx >= visited.length || nx < 0 || ny >= visited[0].length || ny < 0 || map[nx].get(ny) == 'D') {
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                    dist++;
                }
                // 끝이 방문하지 않은 위치일 경우
                if(!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new Pos(nx, ny, t.dist + 1));
                }
                
            }
        }
        return -1;
    }
}

 

2. 구현 로직

1. 로봇과 목표 지점 위치 저장
2. 최소 거리를 탐색하는 문제로 BFS를 활용
3. 상, 하, 좌, 우로 이동할 때, 장애물을 만나거나 벽을 만날 때까지 dist를 증가
4. 해당 위치를 방문한 적이 없다면 방문 체크 후 q에 삽입하며 계속 탐색

 

3. 유의할 점

• 미끄러진다는 점을 고려하여 말의 도착 지점을 구해야할 거 같다.