[프로그래머스 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

 

---

 

입출력 예 설명

 

 

입출력 예 #1

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

 

 

입출력 예 #2

 

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

 

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

 

 

 

나의 코드

import java.util.*;

class Solution {
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};
    char[][] map;
    boolean[][][] visited;
    int[] robot;
    int[] goal; 
    public int solution(String[] board) {
        int answer = 0;
        
        map = new char[board.length][board[0].length()];
        visited = new boolean[board.length][board[0].length()][4];
        robot = new int[2];
        goal = new int[2];
        
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                map[i][j] = board[i].charAt(j);
                if(map[i][j] == 'R') {
                    robot[0] = i;
                    robot[1] = j;
                }
                if(map[i][j] == 'G') {
                    goal[0] = i;
                    goal[1] = j;
                }
            }
        }
        
        answer = bfs();
        
        return answer;
    }
    
    public int bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(robot[0], robot[1], 0));
        
        while(!q.isEmpty()) {
            Node now = q.poll();
            
            if(now.x == goal[0] && now.y == goal[1]) return now.cost;
            
            for(int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length || map[nx][ny] == 'D' || visited[nx][ny][i]) continue;
            
                visited[nx][ny][i] = true;
                
                while(true) {
                    nx += dx[i];
                    ny += dy[i];
                    
                    if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length || map[nx][ny] == 'D') {
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                    
                    visited[nx][ny][i] = true;
                }
                
                q.add(new Node(nx, ny, now.cost + 1));
            }
        }
        
        return -1;
    }
    
    class Node {
        int x;
        int y;
        int cost;
        
        Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}

 

풀이

1. 방향성을 가진 방문 테이블을 생성하여 bfs를 이용하여 문제를 풀었다. 일직선으로 지나가며 해당 좌표에는 반복해서 들를 수 있지만 같은 방향으로 같은 좌표를 지나가는 것은 반복되는 루트이므로 방향성을 추가하여 체크하였다.
2. 문제를 풀고 다른 풀이를 살펴보니 그냥 이차원 방문 테이블을 설정하여 출발점과 도착점(일직선으로 가다 'D' 앞에서 멈추는 자리)만을 방문 테이블에 체크하며 푸는 방법도 있었다. (해당 도착점에 다시 도착하면 반복되는 루트가 되므로 도착점만 체크하면 되는 것 같다.)
3. char형 이차원 배열 map을 생성하여 주어진 board를 이용하여 map을 초기화 하며 로봇의 시작점인 'R'과 도착점인 'G'가 나오면 해당 좌표를 각각 이차원 배열에 저장한다.
4. 주어진 map의 크기에 4방향을 추가하여 방향성을 갖는 방문 테이블 visited를 생성한다. 
5. 완전탐색 bfs를 이용하여 좌표를 탐색하며 제일 빨리 도착하는 루트를 찾는다.
6. 주어진 좌표의 위치 x, y와 이동한 횟수인 cost를 멤법 변수로 갖는 Node 클래스를 생성한다.
7. Node를 선언 타입으로 하는 Queue를 생성하고 로봇의 시작점과 cost를 0으로 갖는 Node를 생성하여 담아준다.
8. while 문을 돌면서 Queue의 첫 데이터를 꺼내어 해당 위치가 도착점인 'G'라면 해당 cost를 리턴한다.
9. 네 방향으로 한 칸씩 이동하여 해당 위치가 좌표를 벗어나거나 해다 위차가 'D' 이거나 해당 방향의 방문테이블이 체크되어있다면 넘어간다.
10. 그렇지 않다면 해당 위치로 이동하여 방문 테이블을 체크하고 while문을 이용하여 'D'가 나올 때까지 이동하며 방문테이블을 체크한다. 'D' 위치가 되면 한 칸 전으로 돌아간다.
11. 일직선으로 이동이 횟수 1번 이므로 cost를 1 증가시키며 해당 위치를 Queue에 담아주도록 한다.
12. 이렇게 bfs를 돌며 Queue에서 꺼낸 위치가 'G'가 되면 해당 cost가 최소 횟수이므로 그대로 반환하면 된다.