프로그래머스 리코쳇 로봇

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

소스코드

import java.util.*;
class Solution {
    static char[][] map;
    static int Ans, R, C, endR, endC;
    public int solution(String[] board) {
        R = board.length;
        C = board[0].length();
        map = new char[R][C];
        int startR = -1;
        int startC = -1;
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                map[i][j] = board[i].charAt(j); 
                if(map[i][j] == 'R') {
                    startR = i;
                    startC = j;
                }
                else if(map[i][j] == 'G') {
                    endR = i;
                    endC = j;
                }
            }
        }
        bfs(startR, startC);
        return Ans==0?-1:Ans;
    }
    private static void bfs(int startR, int startC){
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(startR, startC, 0));
        boolean[][] v = new boolean[R][C];
        v[startR][startC] = true;
        while(!queue.isEmpty()){
            Point p = queue.poll();
            if(p.r == endR && p.c == endC) {
                Ans = p.cnt;
                return;
            }
            for(int i=0; i<4; i++){
                int nr = p.r + dr[i];
                int nc = p.c + dc[i];      
                while(true){
                    if(nr<0 || nc<0 || nr>=R || nc>=C || map[nr][nc] == 'D'){
                        nr -= dr[i];
                        nc -= dc[i];
                        break;
                    }
                    nr += dr[i];
                    nc += dc[i];
                }
                if(v[nr][nc]) continue;
                v[nr][nc] = true;
                queue.offer(new Point(nr, nc, p.cnt+1));
            }
        }
    }
    private static class Point{
        int r, c, cnt;
        public Point(int r, int c,int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
}

해결 방법

이 문제는 기존의 4방탐색과 다르게 한 방향으로 끝까지 가는 문제이다. 그렇기 때문에 4방 탐색을 하고 한 방향으로 계속 가서 외곽을 벗어나거나 'D'를 만날때 까지 진행하였다. 끝까지 갔다면 도착하기 이전으로 돌아간다.
만약 그 좌표가 이미 방문이 되어있다면? -> 해당 좌표에서 4방 탐색으로 이미 지나갔기 때문에 그 좌표점은 의미가 없다.
방문이 되어있지 않다면? -> 해당 좌표를 방문처리 하고 다시 queue에 넣는다.
이렇게 반복하다가 도착지점에 도착하면 Ans값에 p.cnt값을 넣고 도착하지 못하고 끝난다면 Ans값에는 0이 들어가 있을 것이다.
만약 Ans값이 0이라면 -1을 반환하고 아니라면 Ans를 반환한다.