리코쳇 로봇

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

문제설명

• 주어진 파라미터: String[] board
• 반환값: 목표 지점까지 도달하는데 이동한 횟수 int return
• 격자 모양 게임판 위에 말을 움직이는 게임, 시작위치에서 출발한 뒤 목표 위치에 정확하게 멈추기 위해 최소 몇번 이동이 필요한지 말하는 게임
• 상, 하, 좌, 우 방향으로 끝까지 가는걸 한번의 이동으로 정의
• .은 빈공간, R은 로봇의 처음 위치, D는 장애물, G는 목표지점 의미
• 목표 위치에 도달하지 못할 경우 -1 return

풀이방식

1. 최소 횟수를 구하는 문제기 때문에 BFS로 해결한다.
   • 방문 배열과 큐 만들기
   • 시작 정점 정보를 큐에 넣고 방문 처리
   • 큐가 빌때까지 반복
     • 큐에서 정점 정보 꺼내기
     • 꺼내온 정점 사용
     • cur 정점과 인접한 정점 정보 들여다보기
       • 이미 방문 했으면 지나가기
       • 방문하지 않았으면 queue에 넣고 방문 체크하기
2. String[]을 이중 배열로 변환한다(시작:1, 도착:2, 장애물:3)
3. 한번의 이동은 배열의 끝이나 장애물에 도달했을때 멈춘다.
   • 끝까지 간다는 의미는 장애물에 도달했거나 배열의 끝에 도달했을때를 말한다.
   • 이 전의 위치를 기억했다가 도달했을때 해당 위치를 큐에 저장한다.
4. 지나친 곳은 visited 체크하지않는다 → 멈춘 곳만 visited 체크한다.

코드

import java.util.*;

class Solution {
    
    static int[][] graph;
    static boolean[][] visited; 
    static int[] dr = {-1,1,0,0}; // 상, 하, 좌, 우 
    static int[] dc = {0,0,-1,1};
    static int rowLength;
    static int columnLength;
    
    // graph 경계 내에서 움직이고 장애물이 아닐 경우 
    public static boolean isValid(int r, int c){
        return (r >=0 && r < rowLength) && ( c >= 0 && c < columnLength) && (graph[r][c] != 3);
    }
    
    public int solution(String[] board) {
        
        // 저장할 int[][] 배열 생성
        rowLength = board.length;
        columnLength = board[0].length();
        graph = new int[rowLength][columnLength];
        visited = new boolean[rowLength][columnLength];
        int startR = 0;
        int startC = 0;
        
        // String[]을 int[][]로 변환 
        // 시작점: 1, 도착점: 2, 장애물: 3
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length(); j++){
                char current = board[i].charAt(j);
                if(current == '.'){
                    graph[i][j] = 0;
                } else if(current == 'R'){
                    graph[i][j] = 1; // 시작 위치 
                    startR = i;
                    startC = j;
                } else if(current == 'G'){
                    graph[i][j] = 2; // 도착 위치
                } else if(current == 'D'){
                    graph[i][j] = 3; // 장애물 위치 
                }
            }
        }
        
        int count = bfs(startR, startC); // 시작 위치
            
        return count;
    }
    
    public static int bfs(int r, int c){
        Queue<int[]> q = new ArrayDeque<>();
        
        // 초기 세팅 
        q.offer(new int[]{r, c, 0}); // row, column, distance 
        visited[r][c] = true;
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int curRow = cur[0];
            int curCol = cur[1];
            int distance = cur[2];
            
            // 도착지에 도착
            if(graph[curRow][curCol] == 2){
                return distance;
            }
            
            for(int i = 0; i < 4; i++){
                int nextRow = curRow;
                int nextCol = curCol;
                
                // 한 방향으로 끝까지 이동
                while(true){
                    int tempRow = nextRow + dr[i];
                    int tempCol = nextCol + dc[i];
                    
                    if(!isValid(tempRow, tempCol)){
                        break;
                    }
                    
                    nextRow = tempRow;
                    nextCol = tempCol;
                }
                
                if(!visited[nextRow][nextCol]){
                    q.offer(new int[]{nextRow, nextCol, distance + 1});
                    visited[nextRow][nextCol] = true;
                }
            }
        }
        
        return -1; 
    }
}

회고

인접 리스트를 활용한 간단한 BFS를 보다가 격자로 이동하는걸 풀어보니 굉장히 어려웠다.

격자로 이동하는것과 친해져야겠다!

---

참 쉽쥬잉~?~?