[알고리즘] 프로그래머스 JAVA 리코쳇로봇 - BFS 해결

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

프로그래머스

package Programmers;
import java.util.LinkedList;
import java.util.Queue;

public class 리코쳇로봇 {

    static int[] dx = {0, 1,0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static int targetX, targetY, stX, stY, answer;
    static String[][] myBoard;
    static String[][] chMap;
    static Queue<Node> q = new LinkedList<>();

    public static void main(String[] args){
        String[] board = {".D.R", "....", ".G..", "...D"};
        리코쳇로봇 T = new 리코쳇로봇();
        T.solution(board);
    }
    public int solution(String[] board) {
        answer = 0;

        myBoard = new String[board.length][board[0].length()];
        chMap = new String[board.length][board[0].length()];

        for (int i = 0; i < myBoard.length; i++) {
            for (int j = 0; j < myBoard[0].length; j++) {
                myBoard[i][j] = String.valueOf(board[i].charAt(j));
                chMap[i][j] = String.valueOf(board[i].charAt(j));

                //시작지점 저장
                if(String.valueOf(board[i].charAt(j)).equals("R")){
                    stX = j;
                    stY = i;
                    q.offer(new Node(stX, stY));
                }
                //종착지점 도착
                if (String.valueOf(board[i].charAt(j)).equals("G")){
                    targetX = j;
                    targetY = i;
                }
            }
        }

        return bfs();
    }

    private int bfs() {
        int L = 0;
        while (!q.isEmpty()) {
            int len = q.size();
            //레벨측정하기위해서 k for문을 돈다
            for (int k = 0; k < len; k++) {
                Node t= q.poll();
                if (targetX == t.x && targetY == t.y) return L;
                //12시방향부터 시게방향으로 4번 방향 회전
                for (int i = 0; i < 4; i++) {
                    int nx = t.x;
                    int ny = t.y;

                    //i번째 방향을 D를 만나 거나 좌표를 넘어갈때까지 더한다.
                    while (true) {
                        nx += dx[i];
                        ny += dy[i];
                        //좌표계를 넘어가는지 측정
                        if(nx < 0 || nx >= myBoard[0].length || ny < 0 || ny >= myBoard.length){
                            //넘어간다면 이전지점으로 좌표를 돌린다.
                            nx -= dx[i];
                            ny -= dy[i];
                            //왔던곳이거나 시작지점일경우 종료
                            if(chMap[ny][nx] == "X" || chMap[ny][nx] == "R") break;
                            //처음오는곳일경우 체크맵과 노드 추가
                            chMap[ny][nx] = "X";
                            q.offer(new Node(nx, ny));
                            break;
                        }
                        if(myBoard[ny][nx].equals("D")){
                            //넘어간다면 이전지점으로 좌표를 돌린다.
                            nx -= dx[i];
                            ny -= dy[i];
                            //왔던곳이거나 시작지점일경우 종료
                            if(chMap[ny][nx] == "X" || chMap[ny][nx] == "R") break;
                            //처음오는곳일경우 체크맵과 노드 추가
                            chMap[ny][nx] = "X";
                            q.offer(new Node(nx, ny));
                            break;
                        }
                    }//end while
                }//end for i
            }
            L++;
        }
        return -1;
    }
}

class Node{
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

주의할점은 k for 문 돌때 q.size 로 명시해주면 for문안에서 계속 q 가 늘어나기때문에 끝나지 않음 조심