169199. 리코챗 로봇

문제

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

프로그래머스

제한사항

풀이

import java.util.*;

class Solution {
    public int solution(String[] board) {
        int answer = 0;
        
        int n = board.length;
        int m = board[0].length();
        
        char[][] boardMap = new char[n][m];
        int[] start= new int[2];
        int[] end= new int[2];
        
        for(int i =0;i< n;i++)
            for(int j =0; j<m;j++) {
                char position = board[i].charAt(j);
                if(position == 'R')
                    start = new int[]{i,j};
                else if(position == 'G')
                    end = new int[]{i,j};
                
                boardMap[i][j] = board[i].charAt(j);
            }

        boolean[][] visited = new boolean[n][m];
        
        System.out.println("start: " + start[0] + "," + start[1]);
        answer = bfs(visited, boardMap, start, end);
        
        return answer;
    }
    
    int bfs(boolean[][] visited, char[][] boardMap, int[] start, int[] end) {
        Queue<int[]> queue = new LinkedList<>();
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int n = boardMap.length;
        int m = boardMap[0].length;
        
        queue.offer(new int[]{start[0], start[1], 0});
        
        while(!queue.isEmpty()) {
            
            int[] cur = queue.poll();
            int curRow = cur[0];
            int curCol = cur[1];
            int moves = cur[2];
            
            if(curRow == end[0] && curCol == end[1])
                return moves;
            
            for(int i = 0;i<4;i++) {
                int nextRow = curRow;
                int nextCol = curCol;
                
                
                while(nextRow+dir[i][0] >= 0 && nextRow+dir[i][0] < n &&
                     nextCol + dir[i][1] >= 0 && nextCol + dir[i][1] < m &&
                     boardMap[nextRow+dir[i][0]][nextCol+dir[i][1]]!='D') {
                    
                    nextRow+=dir[i][0];
                    nextCol+=dir[i][1];
                    
                }
                
                if(!visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    queue.offer(new int[]{nextRow, nextCol, moves+1});
                }
            }
        }
        
        return -1;
    }
}

회고

BFS를 이용해 최단 이동 횟수를 구하는 문제였다. 일반적인 BFS에서는 한 칸씩 이동하며 방문 여부를 확인하지만, 이 문제에서는 로봇이 장애물이나 벽을 만날 때까지 계속 직진한다. 한 방향을 멈추지 않고 이동하는 코드는 아래와 같다.

while(nextRow+dir[i][0] >= 0 && nextRow+dir[i][0] < n &&
                     nextCol + dir[i][1] >= 0 && nextCol + dir[i][1] < m &&
                     boardMap[nextRow+dir[i][0]][nextCol+dir[i][1]]!='D') {
                    
                    nextRow+=dir[i][0];
                    nextCol+=dir[i][1];
                    
                }

 

여러 방향으로 이동하며 탐색을 하면서 방문 여부를 확인을 해야 무한 이동을 방지할 수 있다. 일반적인 BFS 문제는 한 칸마다 방문 여부를 확인하면 됐었는데, 이 문제는 어떤 방식으로 방문을 확인해야 할지 고민했었다. 근본적인 물음에서 고민이 해결됐다. 왜 일반적인 BFS에서는 한 칸 씩 이동하면서 방문을 확인했을까? 

1. 이동한 칸마다 경우의 수가 달라질 수 있기 때문이다.
2. 방문한 칸이라면 뒤에 일어날 일은 알고 있기 때문에 고려하지 않아도 된다.

하지만 이 문제에서는 한 칸씩 이동해도 경우가 달라지지 않는다. 로봇은 벽이나 장애물을 만나기 전까지 방향을 바꿀 수 없기 때문이다.

그렇다면 중요한 건 이동 중 지나친 칸이 아니라, 로봇이 멈추게 되는 칸이다. 즉, 방문 여부 체크는 멈추는 지점(벽이나 장애물 앞)에서만 하면 충분하다.

좀 더 쉽게 생각하면, 이 문제는 일반적인 BFS에서 각 칸을 하나의 긴 통로로 연결된 형태로 생각할 수 있다. 긴 통로를 따라 로봇이 미끄러지듯이 이동하고, 끝에서 멈추는 순간에만 다음 탐색 가능성을 체크한다고 보면 이해하기 쉽다.