LV2 - 리코쳇 로봇 (Java)

 

---

 

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=java

프로그래머스

 

 

풀이

bfs 문제이다. 단 조금 신경써야 할 것이 있는데, 한 쪽 방향 끝으로 간다는 것이다.

 

첫째론 로봇이 언제 멈추는지 정의할 필요가 있다. 

1. 범위를 벗어났을 때

2. 장애물을 만났을 때

 

두번째로는 동일한 곳에 방문했을때 처리를 어떻게 해줄것인가다.

이거는 해당하는 칸에 몇번만에 방문했는지를 기억하면 된다.

최소횟수 답을 구하기 때문에 이전에 여기 온 횟수보다 짧게 왔다면 추가 탐색을 하고, 아니면 더 할 필요가 없다.

 

시작점에서 4방향으로 모두 이동한다. 한 방향으로 이동할때 멈추는 조건을 만날때까지 이동한다.

단! 이때 내가 탐색을 시작하는 지점에 내가 최소횟수로 왔는지를 확인해야한다. 최소횟수로 왔다면 로직을 수행하고, 그게 아니라면 로직을 수행하지 않는다.

 

그렇게 진행중에 만약 멈추는 조건에 걸린다면 한칸 뒤로 물러준다. 현재 로봇이 있는곳이 범위르 벗어난곳이나 장애물 위치기 때문이다.

 

그리고 로봇이 서있는곳을 확인하고, 여기가  골 칸인지 확인한다.

정답칸이라면 정답칸의 현재 기록되어있는 방문 횟수와, 현재 여기를 방문할때 걸린 횟수중 최소값으로 설정한다.

 

만약 골 칸이 아니라면, 탐색을 계속해야하므로 queue에 넣어준다.

 

코드

import java.util.*;

class Solution {
    
    static class Node {
        public int x;
        public int y;
        public int cnt;

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

    public int[] dx = {0, 0, -1, 1};
    public int[] dy = {1, -1, 0, 0};
    
    public int solution(String[] array)  {

        // Initialize
        List<ArrayList<String>> board = new ArrayList<>();
        int r = array.length;
        int c = 0;
        for (int i = 0; i < r; i++) {
            String[] split = array[i].split("");
            c = split.length;
            board.add(new ArrayList<>(Arrays.asList(split)));
        }

        int[][] visited = new int[r][c];
        for (int i = 0; i < r; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }


        Node startPoint = null;
        Node endPoint = null;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if(board.get(i).get(j).equals("R"))  startPoint = new Node(i, j, 0);
                if(board.get(i).get(j).equals("G"))  endPoint = new Node(i, j, 0);
            }
        }

        // 시작지점에서 bfs 를 한다.
        // bfs는 항상 4방향 모두 취한다.
        // 다음 방문점은 그 방향의 끝이다.

        Deque<Node> queue = new ArrayDeque<>();
        queue.add(startPoint);

        while(!queue.isEmpty()){
            Node currentNode = queue.removeFirst();
            int x = currentNode.x;
            int y = currentNode.y;
            int cnt = currentNode.cnt;

            // 이 지점을 더 많은 횟수로 왔다면 pass 한다.
            if(visited[x][y] <= cnt) continue;

            visited[x][y] = cnt; // 현 도착점에 내가 몇번만의 이동에 왔는지 갱신한다.

            // 4방향 모두 탐색한다.
            for (int i = 0; i < 4; i++) {

                int nx = x;
                int ny = y;

                // 해당 방향 끝까지 이동한다.
                while(true){
                    nx += dx[i];
                    ny += dy[i];

                    // 범위를 벗어나거나 장애물을 만나면 탐색을 멈춰야 한다. (도착점)
                    if(nx < 0 || nx >= r || ny < 0 || ny >= c || board.get(nx).get(ny).equals("D")){

                        // 한 칸 뒤로 무른다.
                        nx -= dx[i];
                        ny -= dy[i];

                        // 만약 여기가 골 지점이었다면? 탐색을 그만한다.
                        if(board.get(nx).get(ny).equals("G")){
                            visited[nx][ny] = Math.min(visited[nx][ny], cnt+1);
                            break;
                        }
                        
                        // 아니라면 추가 탐색을 위해 queue에 넣는다.
                        queue.addLast(new Node(nx, ny, cnt+1));
                        break;
                    }
                }
            }
        }
        
        int ex = endPoint.x;
        int ey = endPoint.y;

        return visited[ex][ey] == Integer.MAX_VALUE ? -1 : visited[ex][ey];
    }
}

 

후기