[프로그래머스 Level 2] 리코쳇 로봇 (Java)

🚀링크

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

💻문제

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

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

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한 사항

• 3 ≤ board의 길이 ≤ 100
  • 3 ≤ board의 원소의 길이 ≤ 100
  • board의 원소의 길이는 모두 동일합니다.
  • 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
  • "R"과 "G"는 한 번씩 등장합니다.

입출력 예

board result
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."] 7
[".D.R", "....", ".G..", "...D"] -1

🌏문제 풀이

BFS를 사용하면 해결할 수 있는 문제입니다. 말이 한 번에 여러칸을 이동할 수 있다는 점과 고려해야할 예외 사항이 많아서 생각보다 까다로운 문제였습니다.

우선, "R"의 현재 x, y 좌표와 이동 횟수를 기록하기 위한 Info 객체를 생성하였고, 이를 우선순위 큐의 데이터 타입으로 설정했습니다. 그 다음은 BFS 알고리즘을 사용하여 말이 상하좌우로 이동하여 "G"에 도달할 수 있는 최소 이동 횟수를 구하면 문제를 해결할 수 있습니다.

💻코드

import java.util.*;

class Solution {
    
    static class Info {
        private int x;
        private int y;
        private int count;
        
        public Info(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    
    static int N, M, start_x, start_y, dest_x, dest_y;
    static boolean[][] visit;
    static char[][] map;
    static int[][] move = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 아래, 오른쪽, 위, 왼쪽
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        map = new char[N][M];
        visit = new boolean[N][M];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                char c = board[i].charAt(j);
                if(c == 'R') {
                    start_x = i;
                    start_y = j;
                }
                if(c == 'G') {
                    dest_x = i;
                    dest_y = j;
                }
                map[i][j] = c;
            }
        }
        
        int answer = bfs();
        
        return answer;
    }
    
    static int bfs() {
        PriorityQueue<Info> pq = 
            new PriorityQueue<>((o1, o2) -> (o1.count - o2.count));
        
        pq.add(new Info(start_x, start_y, 0));
        
        while(!pq.isEmpty()) {
            Info info = pq.poll();
            int curr_x = info.x; // 현재 R의 x좌표
            int curr_y = info.y; // 현재 R의 y좌표
            int cnt = info.count; // 지금까지 움직인 총 횟수
            
            if(curr_x == dest_x && curr_y == dest_y) { // G에 도달한 경우
                return cnt;
            }
            
            if(visit[curr_x][curr_y]) continue; // 이미 방문한 위치일 경우
            
            visit[curr_x][curr_y] = true;
            
            for(int i = 0; i < 4; i++) {
                int rx = move[i][0];
                int ry = move[i][1];
                
                int nx = curr_x, ny = curr_y;
                while(true) {
                    // 현재 좌표가 (0, 0)이고, 움직일 방향이 위쪽이나 왼쪽인 경우
                    if(nx == 0 && ny == 0 && map[nx][ny] != 'D') {
                        if(i == 2 || i == 3) {
                            pq.add(new Info(nx, ny, cnt + 1));
                            break;
                        }
                    }
                    // 현재 좌표가 (0, M - 1)이고, 움직일 방향이 위쪽이나 오른쪽인 경우
                    if(nx == 0 && ny == M - 1 && map[nx][ny] != 'D') {
                        if(i == 1 || i == 2) {
                            pq.add(new Info(nx, ny, cnt + 1));
                            break;
                        }
                    }
                    // 현재 좌표가 (N - 1, 0)이고, 움직일 방향이 아래쪽이나 왼쪽인 경우
                    if(nx == N - 1 && ny == 0 && map[nx][ny] != 'D') {
                        if(i == 0 || i == 3) {
                            pq.add(new Info(nx, ny, cnt + 1));
                            break;
                        }
                    }
                    // 현재 좌표가 (N - 1, M - 1)이고, 움직일 방향이 아래쪽이나 오른쪽인 경우
                    if(nx == N - 1 && ny == M - 1 && map[nx][ny] != 'D'){
                        if(i == 0 || i == 1) {
                            pq.add(new Info(nx, ny, cnt + 1));
                            break;
                        }
                    }
                    
                    // 아래쪽으로 움직이는데 아래쪽 끝에 도달한 경우
                    if(i == 0 && nx == N - 1 && map[nx][ny] != 'D') {
                        pq.add(new Info(nx, ny, cnt + 1));
                        break;
                    }
                    // 오른쪽으로 움직이는데 오른쪽 끝에 도달한 경우
                    if(i == 1 && ny == M - 1 && map[nx][ny] != 'D') {
                        pq.add(new Info(nx, ny, cnt + 1));
                        break;
                    }
                    // 위쪽으로 움직이는데 위쪽 끝에 도달한 경우
                    if(i == 2 && nx == 0 && map[nx][ny] != 'D') {
                        pq.add(new Info(nx, ny, cnt + 1));
                        break;
                    }
                    // 왼쪽으로 움직이는데 왼쪽 끝에 도달한 경우
                    if(i == 3 && ny == 0 && map[nx][ny] != 'D') {
                        pq.add(new Info(nx, ny, cnt + 1));
                        break;
                    }
                    
                    // 장애물에 도달한 경우
                    if(map[nx][ny] == 'D') {
                        // 도달하기 전의 좌표를 추가
                        pq.add(new Info(nx - rx, ny - ry, cnt + 1));
                        break;
                    }
                    
                    // 위의 모든 경우에 해당하지 않으면, 말을 이동시킴
                    nx += rx;
                    ny += ry;
                }
            }
        }
        
        return -1;
    }

}