리코쳇 로봇(Java)

🎯문제

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

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

이 게임에서 말의 움직임은 상, 하, 좌, 우 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"는 한 번씩 등장합니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 문제 설명의 예시와 같습니다.

입출력 예 #2

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

• "R" 위치에 있는 말을 어떻게 움직여도 "G" 에 도달시킬 수 없습니다.
• 따라서 -1을 return 합니다.

✏️풀이

코드

import java.util.*;

class Solution {
	// 이동할 때 사용할 x, y좌표 배열
    int[] dx = { -1, 0, 1, 0 };
    int[] dy = { 0, 1, 0, -1 };
    // 게임판
    char[][] map;
    // 게임판의 세로, 가로
    int n, m;
    // bfs 탐색 메서드
    public int bfs(int rx, int ry, int gx, int gy) {
    	// 큐를 생성
        Queue<int[]> q = new LinkedList<>();
        // 초기 위치와 탐색횟수를 저장
        q.offer(new int[]{rx, ry, 0});
        
        // 방문여부를 저장할 배열 생성
        boolean[][] visit = new boolean[n][m];
        visit[rx][ry] = true;
        
        // 큐에 값이 없을 때까지 반복
        while(!q.isEmpty()) {
        	// 큐에서 값을 가져옴
            int[] now = q.poll();
            int nx = now[0];
            int ny = now[1];
            int move = now[2];
            
            // 가져온 위치가 목적지의 위치와 동일할 경우
            if(nx == gx && ny == gy) {
            	// 탐색횟수를 반환
                return move;
            }
            
            for(int i = 0; i < 4; i++) {
                int mx = nx + dx[i];
                int my = ny + dy[i];
                
                // 장애물에 부딪히거나 벽에 부딪힐 때까지 이동
                while(mx >= 0 && my >= 0 && mx < n && my < m && map[mx][my] != 'D') {
                    mx += dx[i];
                    my += dy[i];
                }
                
                // 부딪히기 전 위치를 저장
                mx -= dx[i];
                my -= dy[i];
                
                // 방문한 적 있거나 시작 위치와 동일할 경우 continue
                if(visit[mx][my] || (mx == nx && my == ny)) {
                    continue;
                }
                
                // 방문여부를 true로 바꿔줌
                visit[mx][my] = true;
                // 큐에 값을 저장
                q.offer(new int[]{ mx, my, move+1 });
            }
        }
        
        // 목적지로 갈 수 없으므로 -1 반환
        return -1;
    }
    public int solution(String[] board) {
    	// 게임판의 세로, 가로 저장
        n = board.length;
        m = board[0].length();
        // 게임판의 크기 설정
        map = new char[n][m];
        // 로봇의 시작 위치와 목적지 위치를 저장
        int rx = 0, ry = 0, gx = 0, gy = 0;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
            	// map에 값을 저장
                map[i][j] = board[i].charAt(j);
                // 값이 R이라면
                if(map[i][j] == 'R') {
                	// 시작위치를 저장
                    rx = i;
                    ry = j;
                }
                // 값이 G라면
                else if(map[i][j] == 'G') {
                	// 종료위치를 저장
                    gx = i;
                    gy = j;
                }
            }
        }
        
        // bfs 탐색이 진행된 뒤 나온 값을 반환
        return bfs(rx, ry, gx, gy);
    }
}

설명

bfs 탐색을 사용해서 진행하였다.

탐색할 시작위치와 종료위치를 매개변수로 받아온다.

bfs 탐색은 큐를 사용해서 진행한다. 따라서 큐를 생성한 뒤에 초깃값인 rx, ry 그리고 탐색횟수인 0을 int[]형으로 저장해준다.

큐에 값이 없을 때까지 반복을 진행하며 큐의 값을 하나 가져와서 위치를 옮겨가면서 탐색을 진행한다. 한번 이동할 때 벽에 부딪히거나 장애물에 부딪힐 때까지 이동을 해야하므로 while문을 사용해서 부딪힐 때까지 이동을 시켜준다.

만일 부딪혔다면 부딪히기 전 위치를 저장해준다.

저장된 위치가 방문한 적 있거나 시작위치와 동일한 경우 다음 탐색으로 넘어간다. 그렇지 않다면 방문여부를 true로 바꿔준 뒤 큐에 값을 저장하는데 이때 탐색 횟수는 move + 1이 된다.

이렇게 탐색하는 도중 큐에서 가져온 위치가 목적지 위치와 같을 경우 해당 탐색횟수를 반환해준다. 그러나 모든 반복문이 끝났을 경우 해당 위치로 갈 수 없다는 뜻이므로 -1을 반환해준다.

solution 메서드에서는 반복문을 사용하여 map에 값을 저장하고 R과 G를 찾아서 각각 rx, ry와 gx, gy에 위치를 저장한다. 이후 bfs 메서드에 매개변수로 값을 넘겨주고 나온 값을 반환해주면 문제를 해결할 수 있다!

💡느낀 점

이번 문제도 bfs 탐색을 이용해서 해결할 수 있었다. 의도한 건 아니지만 연속해서 bfs 문제를 풀다보니 많이 익숙해져서 좋은 것 같다. 이번 문제의 특이한 점은 한번의 이동이 아닌 벽이나 장애물에 부딪힐 때까지 이동을 시켜줘야한다는 점이었다. 해당 부분을 생각해내기 위해서 시간이 걸렸지만 while문을 사용해서 간단하게 구현할 수 있었다. bfs 문제라고 다 똑같은 것이 아니라 탐색의 기준이 살짝씩 달라서 재미있었다.

링크

문제 링크