[프로그래머스] 리코쳇 로봇 Lv2 JAVA [BFS][엄탱]

문제 링크

프로그래머스

문제 설명

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

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

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

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

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

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

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

문제 요약

간단히 요약하자면, 처음 위치 R에서 목표 지점 G까지 최소 움직임을 구하는 문제다. 단 이동 할 때 한 칸씩 이동하는 게 아니라 장애물 D 이거나 board 보드를 벗어나기 전까지 멈추지 않고 쭈욱 이동한다고 보면 된다.

이때 G까지 가는 최소 움직임을 return 해주면 된다.

해설

이번 해설은 BFS 탐색을 모르면 이해하기 힘들 수 있습니다.

우선, 최소 이동거리를 보장해야 하기 때문에, 너비 우선 탐색(BFS)을 사용하면 효율적이다.

DFS보다 BFS가 효율적인 이유는 링크를 클릭하면 확인 할 수 있습니다.

해당 문제는 목적지 까지 최소 움직임을 알기 위한 탐색 문제에서 한 가지만 수정하면 되는 문제이다.

바로, 한칸 이동을 멈출 때까지 이동으로 변경만 해주면 된다. 

 

미끄러지는 부분만 코드를 잠깐 설명을 해보겠다!

for (int i = 0; i < 4; i++) {
   int x = cur.x + X[i];
   int y = cur.y + Y[i];
   
   while(x >= 0 
    	&& y >= 0 
    	&& x < board.length 
    	&& y < board[0].length() 
    	&& board[x].charAt(y) != 'D'
    ) {
    	x += X[i];
        y += Y[i];
    }
                
    x -= X[i];
    y -= Y[i];
}

처음에 방향을 정해주고, while문을 사용해서 끝까지 이동해 주면 x, y 위치가 D이거나 board를 벗어나게 되면 while문에서 나오게 됩니다. 

그 후에 x, y를 한번만 빼주게 되면 딱 장애물 전, board 벗어나기 전으로 돌아가게 됩니다.

전체 코드는 아래에서 확인하면 됩니다.

코드

import java.util.*;

class Solution {
    //        동, 서, 남, 북
    int[] X = {0, 0, 1, -1};
    int[] Y = {1, -1, 0, 0};
    
    public int solution(String[] board) {
        int answer = Integer.MAX_VALUE;
        
        int[] start = findPosition('R', board);
        
        boolean[][] visited = new boolean[board.length][board[0].length()];
        visited[start[0]][start[1]] = true;
        
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(start[0], start[1], 0));
        
        while(!q.isEmpty()) {
            Node cur = q.poll();
            
            if (answer <= cur.count) {
                continue;
            }
            
            if (board[cur.x].charAt(cur.y) == 'G') {
                answer = Math.min(answer, cur.count);
                continue;
            }
            
            for (int i = 0; i < 4; i++) {
                int x = cur.x + X[i];
                int y = cur.y + Y[i];
                
                if (x < 0 || y < 0 || x >= board.length || y >= board[0].length()) {
                    continue;
                }
                
                if (board[x].charAt(y) == 'D') {
                    continue;
                }
                
                while(x >= 0 && y >= 0 
                      && x < board.length && y < board[0].length()
                      && board[x].charAt(y) != 'D') {
                    x += X[i];
                    y += Y[i];
                }
                
                x -= X[i];
                y -= Y[i];
                if (visited[x][y]) {
                    continue;
                }
                
                
                visited[x][y] = true;
                
                q.offer(new Node(x, y, cur.count + 1));
            }
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    private int[] findPosition(char find, String[] board) {
        for (int i = 0; i < board.length; i++) {
            String s = board[i];
            
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == 'R') {
                    return new int[]{i, j};
                }
            }
        }
        
        return null;
    }
}

class Node {
    int x;
    int y;
    int count;
    
    public Node(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}