catsridingCATSRIDING|OCEANWAVES
Challenges

Programmers | Level 2 | 리코쳇 로봇

jynn@catsriding.com
Sep 23, 2024
Published byJynn
999
Programmers | Level 2 | 리코쳇 로봇

Programmers | Level 2 | 리코쳇 로봇

Problems

  • 📘 Src: Programmers
  • 🗂️ Cat: Breadth-First Search

󰧭 Description

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

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 출발한 뒤 목표 위치에 정확하게 멈추기 위해 최소 몇 번의 이동이 필요한지 말하는 게임입니다.

이 게임에서 말의 이동은 현재 위치에서 상, 하, 좌, 우 중 한 방향으로 게임판 위의 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.

다음은 보드게임판을 나타낸 예시입니다. ("."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.)

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

이때 최소 움직임은 7번이며 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 "G" 위치에 멈춰 설 수 있습니다.

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

 Constraints

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

󰦕 Examples

boardresult
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]7
["...D..R", ".D....", "....D.D", "D....D.", "..D.G.."]-1

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    // 상하좌우로 이동하기 위한 델타 배열
    private static final int[] dx = {0, 1, 0, -1};
    private static final int[] dy = {1, 0, -1, 0};
    
    public int solution(String[] board) {
        int rows = board.length;
        int cols = board[0].length();
        int[][] grid = new int[rows][cols];  // 게임판을 2차원 배열로 변환
        boolean[][] marked = new boolean[rows][cols];  // 방문 여부를 기록할 배열
        int[] robot = new int[2];  // 로봇의 시작 위치를 기록
        
        // 게임판 초기화 및 로봇 위치 찾기
        for (int i = 0; i < rows; i++) {
            String row = board[i];
            for (int j = 0; j < cols; j++) {
                if (row.charAt(j) == 'R') {
                    robot = new int[]{i, j};  // 로봇의 시작 위치 저장
                }
                if (row.charAt(j) == 'D') {
                    grid[i][j] = 1;  // 장애물 위치 저장
                }
                if (row.charAt(j) == 'G') {
                    grid[i][j] = 2;  // 목표 위치 저장
                }
            }
        }
        
        // BFS를 통해 최소 이동 횟수 계산
        int result = bfs(grid, marked, robot, rows, cols);
        return result;
    }
    
    // BFS 알고리즘을 통해 목표 위치까지 이동하는 최소 경로 찾기
    private int bfs(int[][] grid, boolean[][] marked, int[] robot, int rows, int cols) {
        Deque<int[]> queue = new ArrayDeque<>();
        int sx = robot[0];
        int sy = robot[1];
        queue.offer(new int[]{sx, sy, 0});  // 초기 위치와 이동 횟수 0을 큐에 추가
        marked[sx][sy] = true;  // 시작 위치 방문 처리
        
        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            int cs = current[2];  // 현재 이동 횟수
            
            // 4방향 탐색 (우, 하, 좌, 상)
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + cx;
                int ny = dy[i] + cy;
                int ns = cs + 1;
                
                // 벽이나 장애물에 부딪힐 때까지 이동
                while (!isWall(nx, ny, grid, rows, cols)) {
                    nx += dx[i];
                    ny += dy[i];
                }
                
                // 벽이나 장애물 전 위치에서 멈춤
                nx -= dx[i];
                ny -= dy[i];
                
                // 목표 지점에 도달하면 이동 횟수 반환
                if (grid[nx][ny] == 2) return ns;
                
                // 아직 방문하지 않은 위치라면 큐에 추가
                if (!marked[nx][ny]) {
                    marked[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, ns});
                }
            }
        }
        return -1;  // 목표 지점에 도달할 수 없으면 -1 반환
    }
    
    // 벽이나 장애물 또는 범위를 벗어나는지 확인하는 함수
    private boolean isWall(int nx, int ny, int[][] grid, int rows, int cols) {
        return nx < 0 
            || nx >= rows 
            || ny < 0 
            || ny >= cols 
            || grid[nx][ny] == 1;
    }
}

 Approaches

이 문제는 로봇이 벽이나 장애물에 부딪힐 때까지 계속 이동하는 특성을 활용하여 BFS(너비 우선 탐색)으로 해결할 수 있습니다. 각 방향으로 가능한 최대 이동 거리를 탐색한 후, 최소 이동 횟수로 목표 지점에 도달하는 경로를 찾아야 합니다. BFS는 최단 경로 탐색에 적합한 알고리즘으로, 이 문제의 의도는 여러 경로 중에서 가장 빠른 경로를 찾아내는 것입니다.

1. 문제 분석

리코쳇 로봇 문제는 로봇을 시작 위치에서 목표 위치까지 이동시키는 퍼즐 문제입니다. 이 문제의 핵심은 로봇이 상하좌우로 이동할 때 한 칸씩 움직이는 것이 아니라, 벽이나 장애물에 부딪힐 때까지 계속 미끄러지듯 직선으로 이동한다는 점입니다. 각 방향으로 가능한 최대 거리까지 한 번에 이동해야 하기 때문에 일반적인 한 칸씩의 경로 탐색과는 다른 방식으로 문제를 해결해야 합니다. 로봇은 상하좌우로 움직일 수 있으며, 벽이나 장애물에 막힐 때까지 직선으로 이동합니다. 이런 특성으로 인해 로봇은 한 번의 이동에서 여러 칸을 지나칠 수 있습니다.

이 문제의 목표는 로봇이 가능한 최소한의 이동으로 목표 위치인 'G'에 도달하는 경로를 찾는 것입니다. BFS 알고리즘을 사용하여 경로를 탐색하는 것이 적합한데, BFS는 여러 경로를 모두 탐색하면서 가장 먼저 도달하는 경로를 찾아낼 수 있기 때문입니다.

로봇은 한 방향으로 최대한 이동한 후 멈추고, 그 위치에서 다시 다른 방향으로 탐색을 반복합니다. 만약 로봇이 목표 지점에 도달하지 못하는 경우가 발생한다면, 이는 모든 경로를 탐색했음에도 ‘G’로 가는 유효한 경로가 없다는 뜻입니다. 예를 들어, ‘G’로 가는 모든 경로가 벽이나 장애물로 막혀 있거나, 최소 하나 이상의 벽이나 장애물을 등지지 않고 있는 경우입니다. 로봇은 장애물에 부딪힐 때만 멈출 수 있기 때문에, ‘G’가 벽이나 장애물에 인접해 있지 않으면 로봇은 그 지점을 지나쳐버리거나 도달할 수 없습니다. 이러한 경우 문제는 -1을 반환하여 목표 지점에 도달할 수 없음을 의미합니다.

2. 접근 방식

리코쳇 로봇 문제는 로봇이 한 번에 여러 칸을 건너뛰며 장애물이나 벽에 부딪힐 때까지 미끄러지는 특성 때문에, 일반적인 경로 탐색 문제와는 다소 차이가 있습니다. 이 문제는 BFS 알고리즘을 사용하여 최단 경로를 탐색하는 방식으로 해결할 수 있습니다.

BFS는 최단 경로를 찾는 데 최적화된 알고리즘으로, 모든 경로를 동일하게 탐색하면서 가장 먼저 목표에 도달하는 경로를 찾아냅니다. BFS의 기본 개념은 큐(Queue)를 사용하여 각 이동을 순차적으로 처리하며, 이동할 수 있는 모든 경로를 차례로 탐색하는 것입니다.

문제 해결을 위한 구체적인 단계는 다음과 같습니다:

  1. 게임판 초기화 및 로봇 시작 위치 찾기: 먼저 주어진 보드 배열을 기반으로 2차원 배열을 생성하여 게임판을 초기화합니다. 각 칸을 탐색하면서 로봇의 시작 위치(R), 장애물(D), 목표 위치(G)를 기록합니다. 이 과정에서 로봇의 초기 위치는 이후 BFS 탐색의 출발점이 됩니다.
  2. BFS 탐색을 위한 큐 초기화: 로봇의 시작 위치를 큐에 넣고 BFS 탐색을 시작합니다. 큐는 현재 위치와 이동 횟수를 저장하며, 각 탐색 단계에서 로봇의 위치를 업데이트합니다.
  3. 4방향으로 가능한 모든 이동 탐색: 로봇은 상하좌우 네 방향으로 움직일 수 있으며, 각 방향으로 장애물이나 벽에 부딪힐 때까지 계속해서 이동합니다. 즉, 한 번의 이동은 여러 칸을 건너뛰어 한 방향으로 끝까지 가는 방식입니다. 이동이 끝나는 위치에서 다시 BFS를 통해 다음 가능한 이동을 탐색합니다.
  4. 목표 지점 도달 여부 확인: 각 이동 단계에서 목표 위치(G)에 도달했는지 확인합니다. 만약 목표 지점에 도달했다면 그때까지의 이동 횟수를 반환하고 탐색을 종료합니다.
  5. 탐색 종료 및 실패 처리: 만약 모든 경로를 탐색했음에도 불구하고 목표 지점에 도달하지 못했다면, 이는 목표 위치에 도달할 수 없다는 의미이므로 -1을 반환합니다.

이 문제의 핵심은 한 번의 이동이 직선으로 끝까지 진행된다는 점입니다. 이를 효율적으로 탐색하기 위해 각 방향으로 가능한 모든 이동을 탐색하고, 이미 방문한 위치는 다시 방문하지 않도록 처리하여 중복된 경로 탐색을 방지해야 합니다. BFS를 사용하면 모든 경로를 균등하게 탐색하므로, 최단 경로를 가장 먼저 찾을 수 있습니다.

3. 게임판 초기화 및 BFS 탐색 준비

게임판을 초기화하려면 먼저 주어진 board 배열을 2차원 배열로 변환해야 합니다. 이 배열을 탐색하면서 로봇의 시작 위치와 장애물, 그리고 목표 위치를 찾아 기록합니다. 로봇의 시작 위치는 'R', 장애물은 'D', 목표 위치는 'G'로 표시되며, 각 위치는 이후 탐색에서 중요한 역할을 하므로 정확하게 기록됩니다.

로봇이 시작할 위치는 이후 BFS 탐색의 출발점으로 활용되며, 이 위치를 추적합니다. 또한, 장애물의 위치는 로봇이 지나갈 수 없는 칸으로 설정되어야 하므로 이를 기록해 두어야 합니다. 목표 위치는 로봇이 도달해야 할 최종 지점으로, 탐색 중 목표 위치에 도달할 경우 탐색을 종료하고 해당 경로의 이동 횟수를 계산하는 데 사용됩니다.

이 단계에서는 단순히 게임판의 각 요소를 탐색하고, 필요한 정보를 적절히 기록해 다음 단계의 탐색을 준비하는 과정입니다.

Solution.java
int rows = board.length;
int cols = board[0].length();
int[][] grid = new int[rows][cols];  // 게임판을 2차원 배열로 변환
boolean[][] marked = new boolean[rows][cols];  // 방문 여부를 기록할 배열
int[] robot = new int[2];  // 로봇의 시작 위치를 기록

// 게임판 초기화 및 로봇 위치 찾기
for (int i = 0; i < rows; i++) {
    String row = board[i];
    for (int j = 0; j < cols; j++) {
        if (row.charAt(j) == 'R') {
            robot = new int[]{i, j};  // 로봇의 시작 위치 저장
        }
        if (row.charAt(j) == 'D') {
            grid[i][j] = 1;  // 장애물 위치 저장
        }
        if (row.charAt(j) == 'G') {
            grid[i][j] = 2;  // 목표 위치 저장
        }
    }
}
4. BFS 탐색 및 경로 찾기

BFS 탐색을 통해 로봇이 목표 지점까지 도달할 수 있는 최단 경로를 구하는 과정은, 로봇이 한 방향으로 벽이나 장애물에 부딪힐 때까지 계속 이동하는 특성을 잘 활용해야 합니다. 로봇은 한 번의 이동에서 여러 칸을 건너뛰며 움직이기 때문에, 이동을 마친 후에는 네 방향 모두를 다시 탐색하여 최적의 경로를 찾아야 합니다.

탐색 과정에서 각 방향으로 로봇을 움직일 때는 먼저 해당 방향으로 벽이나 장애물에 부딪힐 때까지 직선으로 이동하게 됩니다. 장애물이나 벽에 부딪히면 그 전 위치에서 멈추고, 그 위치에서 다시 새로운 방향으로 이동을 시도합니다. 이런 과정을 반복하면서 가능한 모든 경로를 탐색하고, 목표 지점인 'G'에 도달하는 최단 경로를 찾아냅니다.

탐색을 진행하면서 BFS의 특성상 가장 먼저 도달한 경로가 최단 경로가 되므로, 목표 지점에 도달하는 순간 해당 경로의 이동 횟수를 반환하면 됩니다. 만약 모든 경로를 탐색했음에도 목표 지점에 도달하지 못하면, 이는 목표에 도달할 수 없다는 뜻이므로 -1을 반환합니다.

Solution.java
private int bfs(int[][] grid, boolean[][] marked, int[] robot, int rows, int cols) {
    Deque<int[]> queue = new ArrayDeque<>();
    int sx = robot[0];
    int sy = robot[1];
    queue.offer(new int[]{sx, sy, 0});  // 초기 위치와 이동 횟수 0을 큐에 추가
    marked[sx][sy] = true;  // 시작 위치 방문 처리

    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int cx = current[0];
        int cy = current[1];
        int cs = current[2];  // 현재 이동 횟수

        // 4방향 탐색 (우, 하, 좌, 상)
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + cx;
            int ny = dy[i] + cy;
            int ns = cs + 1;

            // 벽이나 장애물에 부딪힐 때까지 이동
            while (!isWall(nx, ny, grid, rows, cols)) {
                nx += dx[i];
                ny += dy[i];
            }

            // 벽이나 장애물 전 위치로 이동
            nx -= dx[i];
            ny -= dy[i];

            // 목표 지점에 도달하면 이동 횟수 반환
            if (grid[nx][ny] == 2) return ns;

            // 아직 방문하지 않은 위치라면 큐에 추가
            if (!marked[nx][ny]) {
                marked[nx][ny] = true;
                queue.offer(new int[]{nx, ny, ns});
            }
        }
    }
    return -1;  // 목표 지점에 도달할 수 없으면 -1 반환
}

로봇이 이동할 수 있는 경로는 벽이나 장애물로 제한되기 때문에, 이동 중에 벽이나 장애물에 부딪혔는지를 확인하는 것이 중요합니다. 이를 위해 보조 함수를 사용하여, 주어진 좌표가 벽이나 장애물에 해당하는지 확인한 후 적절히 처리합니다. 이 보조 함수는 경계를 벗어나거나 장애물에 부딪힌 경우를 감지하고, 이를 통해 로봇의 움직임을 제어합니다.

이 함수는 로봇이 더 이상 전진할 수 없는 경우를 감지하여, 탐색 경로에서 멈추고 다음 경로로 이동하도록 돕습니다.

Solution.java
private boolean isWall(int nx, int ny, int[][] grid, int rows, int cols) {
    return nx < 0 
        || nx >= rows 
        || ny < 0 
        || ny >= cols 
        || grid[nx][ny] == 1;
}
5. 최종 해시 값 도출

모든 경로를 탐색한 후, 목표 지점에 도달할 수 있다면 그때까지의 이동 횟수를 반환하고, 도달할 수 없다면 -1을 반환합니다.

Solution.java
// 목표 지점에 도달한 경우 이동 횟수를 반환, 그렇지 않다면 -1 반환
return result;

이 과정을 통해 로봇이 목표 지점까지 이동하는 데 필요한 최소 이동 횟수를 구할 수 있습니다.

󰄉 Complexity

  • ⏳ TC: O(n * m)
  • 💾 SC: O(n * m)

모든 칸을 한 번씩 탐색해야 하므로 시간 복잡도는 O(n * m)입니다. 또한, 큐와 방문 여부를 기록하는 배열이 필요하므로 공간 복잡도 역시 O(n * m)입니다.

  • Algorithm
  • BFS