프로그래머스 | LV.2 리코쳇 로봇 - BFS 문풀 (Java)

⬛ 프로그래머스 | LV.2 리코쳇 로봇 - BFS 문풀

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

문제 설명

---

💚문제 접근 방식

• 문제 설명은 매우 간단하지만 생각을 잘 해야되는 문제이다. 
• 시작 R위치에서 목표점 G으로 (동,서,남,북) 가서 도착하는 최소 이동 횟수를 구하라고 되어 있다.
• 맨 처음 예제를 보고 든 생각 : 최소 이동하는데, 왜 답이 7씩이나 나오지 ?

일단 방향이 매번 정해질 때마다 (막힌 곳까지) 구슬마냥 쭉 간다. (이게 1번의 이동임)

그리고, 막힌 곳까지 쭉 굴러가다가 G를 (지나치는 건) 목표점 도달이 아니다.
반드시 D든 맨끝이든 부딪혀서 쭉 가다 막혀서 (멈춘 위치가) G여야 목표점 도달이다.

쭉 굴러가면서 벽을 만날 때마다 멈추고, 멈췄다면 그 위치가 매번 방문하는 위치가 된다는 점을 제대로 이해하자.

이동 방법 손풀이

이제 다 깨달았으니 어떻게 풀었는지 설명해보겠다.

1) Node 클래스 선언 (x, y 좌표와 매번 count 횟수 담음)

2) 2차원 char 배열에 입력값 세팅해준다. (이때 시작점 R 좌표도 세팅)

3) BFS 순회를 시도한다.

• while(!Q.isEmpty()) 인 동안 반복하면서
• for문으로 4방향을 처리해줄 때 매번 현재 방향 k에 대한 처리가 다음과 같다.

(1) 다음 방향 k 에서 nx 좌표가 경계 벗어나거나 D인 경우 continue

(2) while 문을 내부적으로 돌면서 nx, ny가 경계 벗어나지 않고, D 장애물 만나지 않은 동안

     현재 방향 k에 대해 nx, ny 를 쭉 이동시키다 = (굴려보낸다)

(3) while을 탈출했다는 건 막혀서 탈출한 거다. 현재 지점을 세팅해줘야 하니 직전 정점으로 한칸씩 돌려보낸다.

(4) 멈춘 이 지점이 방문했던 곳이면 중복처리 되니 continue;

(5) 방문 전인 곳이라면 방문 처리 후 Q에 담을 때, 직전 cur의 count 값에 + 1 해줘서 (이동 횟수 ++)

4) 이제 answer는 목표점 G에 (멈춰서) 도달한 이동 횟수가 담겨 있으면 출력하고, 도달 못해서 갱신 안되었다면 -1 을 출력하도록 한다.

---

💚 제출 코드

import java.util.*;
class Node{
    int x, y, count;
    Node(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }
}
class Solution{
    //4방향
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static char[][] map;
    
    //솔루션 함수 
    public int solution(String[] board) {
        int answer = Integer.MAX_VALUE;
        int N = board.length;
        int M = board[0].length();
        map = new char[N][M];
        
        int[] st = new int[2];
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] = board[i].charAt(j);
                if(map[i][j] == 'R'){ // 시작점 세팅 
                    st[0] = i;
                    st[1] = j;
                }
            }
        }
        
        boolean[][] visited = new boolean[N][M];
        visited[st[0]][st[1]] = true;
        
        Queue<Node> Q = new LinkedList<>();
        Q.offer(new Node(st[0], st[1], 0));
        
        while(!Q.isEmpty()){
            Node cur = Q.poll();
            System.out.println(cur.x  + " " + cur.y + " : "+cur.count);
            if(answer <= cur.count){
                continue;
            }
            if(map[cur.x][cur.y] == 'G'){
                answer = Math.min(answer, cur.count);
                continue;
            }
            
            for(int k=0; k<4; k++){
                int nx = cur.x + dx[k];
                int ny = cur.y + dy[k];
                
                if(nx <0 || ny <0 || nx >= N || ny >= M || map[nx][ny] == 'D') continue;
                
                while(nx >=0 && ny >= 0 && nx < N && ny <M && map[nx][ny] != 'D') {
                    nx += dx[k];
                    ny += dy[k];
                }
                
                nx -= dx[k];
                ny -= dy[k];
                
                if(visited[nx][ny]) continue;
                
                visited[nx][ny] = true;
                Q.offer(new Node(nx, ny, cur.count + 1));
            }
            
        }
        
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}

💚 시간 복잡도

BFS의 시간복잡도는 인접행렬으로 그래프 구현 시 O(V^2) 이고, 인접리스트로 그래프 구현 시 O(V+E) 이다.
이 문제는 인접행렬로 2차원 배열 안을 순회하도록 했기 때문에 O(V^2) 일 것 같은데, 제한 사항에서 board 길이와 board 원소의 길이 모두 100 이하의 값만 들어오기 때문에 2중 for문 돌아도 10,000 이라 시간 내에 동작한다.
N = board 길이
M = board원소의 길이 
둘 다 100 이하의 값만 들어올 수 있어서 O(NXM) 이어도 10,000 이란 소리다.

💚 회고

예전에 이런 식으로 좌표가 한칸 씩 이동하는 게 아니라, 매번 한 방향으로 쭉 굴리는 문제를 풀었던 것 같다. 일단 예제에서 설명하는 풀이도 설명이 자세한 건 아니여서 손으로 직접 그려보면서 왜 그렇게 답이 나올 수밖에 없는지 명확한 사고과정이 필요한 것 같다.