[BFS] 리코쳇 로봇

❓문제

목표 위치까지 멈출 때 최소 이동거리

상, 하, 좌, 우 한 방향으로만 움직임 

장애물이나 가장자리 부딪힐 때까지 직진

---

🖐️손코딩

height, width, visited
dx = {-1, 1, 0, 0}
dy = {0, 0, -1, 1}

bfs(startx, starty, matrix)
	queue.offer([starty, startx, cnt=0])
    visited[starty][startx] = true
    
    while(!queue.isEmpty())
    	info = queue.poll()
        cury = info[0]
        curx = info[1]
        curcnt = info[2]
        
        if(matrix[cury][curx] == 'G')
        	return curcnt;
        
        for(i: 0 ~ 3)
        	ny = cury
            nx = curx
            
            while(ny nx 장애물 없음 + 가장자리 아님)
            	ny += dy
                nx += dx
            
            visited[ny][nx] = true
            queue.offer(ny, nx, curcnt+1)
     return -1

main(String[] board)
	height = board.length
    width = board[0].length()
    
    matrix = char[height][width]
    visited = boolean[height][width]
    
    for(i: 0 ~ height-1)
    	matrix[i] = board[i].toCharArray()
        
    for(i : 0 ~ height-1)
    	for(j: 0 ~ width-1)
        	if (matrix[i][j] == 'G')
            	bfs(j, i, matrix)

---

👩‍💻구현 코드

import java.util.*;

class Solution {
    int height, width;
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    
    private int bfs(int starty, int startx, char[][] matrix){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{starty, startx, 0});
        visited[starty][startx] = true;
        
        while(!queue.isEmpty()){
            int[] info = queue.poll();
            int cury = info[0];
            int curx = info[1];
            int curcnt = info[2];
            
            if(matrix[cury][curx] == 'G'){
                return curcnt;
            }
            
            for(int i = 0; i<4; i++){
                int ny = cury;
                int nx = curx;
                
                while(ny >= 0 && ny < height &&
      nx >= 0 && nx < width &&
      matrix[ny][nx] != 'D'){
                    ny += dy[i];
                    nx += dx[i];
                }
                
                ny -= dy[i];
                nx -= dx[i];
                
                if(!visited[ny][nx]){
                        visited[ny][nx] = true;
                        queue.offer(new int[]{ny, nx, curcnt+1});
                    }
            }
        }
        
        return -1;
    }
    
    public int solution(String[] board) {
        int answer = -1;
        height = board.length;
        width = board[0].length();
        
        char[][] matrix = new char[height][width];
        visited = new boolean[height][width];
        
        for(int i = 0; i<height; i++){
            matrix[i] = board[i].toCharArray();
        }
        
        for(int i = 0; i<height; i++){
            for(int j = 0; j<width; j++){
                if(matrix[i][j] == 'R'){
                    answer = bfs(i, j, matrix);
                }
            }
        }
        
        return answer;
    }
}

---

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

프로그래머스