프로그래머스, 리코쳇 로봇(java)

문제 설명

게임판이 존재할 때, 말이 시작 위치에서 목표까지 최소 몇 번만에 도달할 수 있는지를 구하는  문제이다.

말은 상, 하, 좌, 우 총 4방향 중 하나를 선택해서 움직인다. 이때 장애물이나 벽을 부딪힐 때까지 쭉 움직여야 하는데, 이 움직임 한 번을 한 번 이동한 것으로 친다.

뿐만 아니라 만일 목표 지점에 도착했더라도 주변에 장애물이나 벽이 없어 멈추지 못했다면, 목표 지점을 지나가게 된다.

 

처음 문제를 봤을 때 혼란스러웠던 이유는 저 맨 마지막 조건을 고려하지 않았기 때문이다. 나는 목표점인 'G'까지만 가면 이동이 종료되는 줄 알았으나, 이동의 종료는 무조건 장애물이나 벽을 만날 때만이다. 그러므로 멈출 수 없다면 'G'를 만나도 계속 움직여야 한다.

 

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

프로그래머스

문제 풀이

첫 번째 접근

일단 좌표를 넣어줄 객체를 하나 만들어 준다. 해당 객체에는 열, 행 그리고 각 위치마다의 움직임을 저장한다.

class Pair{
    int row;
    int col;
    int count;
    
    Pair(int row, int col, int count){
        this.row = row;
        this.col = col;
        this.count = count;
    }
}

그리고 주어진 board는 문자열 배열로 되어 있으니 이를 문자 2차원 배열로 만들어 준다. 이때, 시작 점인 'R'이 보이면 Pair 형 start에 해당 값을 넣어준다.

        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length(); j++){
                map[i][j] = board[i].charAt(j);
                if(map[i][j] == 'R'){
                    start = new Pair(i, j, 1);
                } 
            }
        }

이제 너비우선 탐색을 통해서 움직임의 수를 구해줄 차례이다.

너비 우선 탐색을 할 것이니 큐를 하나 만들어 주고 시작 점을 넣어준다. 그리고 해당 위치를 방문했음을 표시한다. 나는 처음에는 최소 값을 구해줘야 한다는 생각에 방문을 표시하지 않았다. 왜냐하면 재방문을 했을 때 최솟값이 나올 수 있다고 생각했기 때문이다.

그러나, 어차피 제일 먼저 'G'에 도착한 경로는 제일 먼저 도착했기 때문에 최솟 값이 된다. 큐는 선입선출로 먼저 들어간 것이 먼저 나오는 자료구조이니, 먼저 'G'에 도착한 것이 최솟 값인 것이다. 만일 방문 표시를 간과하면 'G'로 도달할 수 있는 r경우는 정답이 정확하게 나올 테지만, 도달할 수 없는 경우 무한으로 빠지게 된다.

 

그리고 while문 부터는 우리가 너비우선 탐색을 풀었던 것처럼 해주면 된다. 그러나 각 방향을 정해주고 그 안쪽에는 while문을 하나 더 작성하여 해당 방향만을 가지고 로봇을 이동시켜야 한다.

 

여기서 중요한 것이 있는데, 로봇은 장애물이나 벽에 부딪혔을 때 멈춘다는 것이다. 그러므로 장애물 혹은 벽을 만났을 때 그 직전 위치가 'G'인지 확인하고 만일 그렇다면 해당 방향이 몇 번째인지를 반환하도록 했다. 만일 'G'가 아니라면 break를 해 인덱스 오류가 나지 않도록 처리했다.

 

위의 조건에 해당하지 않으면 새로운 좌표를 만들어 주고 탐색하도록 했다.

 

내부의 while문이 끝나면 nRow와 nCol의 직전 위치를 복구해줬다. 이 이유는 break로 나온 nCol과 nRow는 벽이거나 장애물의 위치이기 때문이다. 그러므로 해당 위치를 기준으로 한 칸 물러서게 한 다음 방문하지 않았으면 방문 표시한 후 큐에 넣어줬다.

 

코드

java

import java.util.*;

class Pair{
    int row;
    int col;
    int count;
    
    Pair(int row, int col, int count){
        this.row = row;
        this.col = col;
        this.count = count;
    }
}

class Solution {
    public static char[][] map;
    public static boolean[][] visit;
    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};
    public static int rowLength, colLength;
    
    public int solution(String[] board) {
        int answer = 0;
        rowLength = board.length;
        colLength = board[0].length();
        map = new char[rowLength][colLength];
        visit = new boolean[rowLength][colLength];
        Pair start = null;
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length(); j++){
                map[i][j] = board[i].charAt(j);
                if(map[i][j] == 'R'){
                    start = new Pair(i, j, 1);
                } 
            }
        }

        answer = bfs(start);
        
        return answer;
    }
    
    public int bfs(Pair start){
        Queue<Pair> queue = new LinkedList<>();
        queue.add(start);
        visit[start.row][start.col] = true;
        
        while(queue.size() != 0){
            Pair current = queue.poll();
            int cRow = current.row;
            int cCol = current.col;
            int cCount = current.count;
            
            for(int i=0; i<4; i++){
                int nRow = cRow + dR[i];
                int nCol = cCol + dC[i];
                
                while(true){
                    
                    if((nRow < 0 || nRow >= rowLength || nCol < 0 || nCol >= colLength) || (map[nRow][nCol] == 'D')){
                        if(map[nRow-dR[i]][nCol-dC[i]] == 'G'){
                            return cCount;
                        }
                        break;
                    }
                    
                    nRow += dR[i];
                    nCol += dC[i];
                }
                nRow -= dR[i];
                nCol -= dC[i];
                if(!visit[nRow][nCol]){
                    visit[nRow][nCol] = true;
                    queue.add(new Pair(nRow, nCol, cCount+1));
                }
                
            }
        }
        
        return -1;
    }
    
}