[Lv.2] 리코챗 로봇

66.7/100 코드

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public static int answer=Integer.MAX_VALUE;
    public int solution(String[] board) {


        //일단 dfs로 .. ㄱ ㄱ
        int x = 0,y=0;
        boolean findFlag=false;
        for (int j=0;j<board.length;j++) {
            if(findFlag)
                break;
            for (int i = 0; i < board[j].length(); i++) {
                if(board[j].charAt(i)=='R'){
                    x=i;
                    y=j;
                    //System.out.println("Found :"+x+"/"+y);
                    findFlag=true;
                    break;
                }
            }
        }


        dfs(board,0,new Point(x,y,board));



        if(answer==Integer.MAX_VALUE)
            return -1;
        return answer;
    }
    //지나친 점을 다시 지나치는 경우는 경로의 최소가 될 수 없음
    //보드를 매 step마다 들고 다니면서 최적의 경로를 찾고 어떤 경로로도 계속 다시 되돌아오면 결국 return이 제대로 되지 않을 것임..
    //지나친 길은 X로 바꾸기
    public void dfs(String[] board, int moveCount,Point point){
        //현재 step의 지점이 G인 경우 return
        //printBoard(board);

        if(board[point.y].charAt(point.x)=='G'){
            //System.out.println("Reached count:"+moveCount);
            answer= Math.min(answer,moveCount);
            return;
        }
        if(moveCount>answer)
            return;

        List<Point> possiblePoint = getPossiblePoint(point, board);
        //이동 가능한 점이 없는 경우 return
        if(possiblePoint.isEmpty())
            return;

        possiblePoint.forEach(pt->{
            dfs(pt.board,moveCount+1,pt);
        });

    }
    public void printBoard(String[] board){
        System.out.println("================print=========================");
        for (String s : board) {
            System.out.println(s);
        }
        System.out.println("================end===========================");
    }
    class Point{
        //0부터 시작( idx값 )
        //첫 입력을 0,0 가로를 x 세로를 y로 한다.
        //즉 board[y].charAt(x)
        int x,y;
        String[] board;

        public Point(int x, int y, String[] board) {
            this.x = x;
            this.y = y;
            this.board=board;
        }

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

    private List<Point> getPossiblePoint(Point point, String[] board){
        List<Point> possiblePoints = new ArrayList<>();
        //LR UD 마다 가능한 지 판단
        //L
        if(point.x>0){
            //벽에 붙어있지 않은 경우 왼쪽 이동을 시도한다.
            String[] leftBoard=board.clone();
            boolean flag=true;
            //해당 방향으로 가는데 지나온길이 장애물이나 벽 전에 존재하면 break ->false
            //X를 만나지않고 벽 혹은 장애물에 도착하는 경우 ->true
            int stopX=0;
            for (int i = point.x-1; i >=0; i--) {
                if(leftBoard[point.y].charAt(i)=='X'){
                    flag=false;
                    break;
                }else if(leftBoard[point.y].charAt(i)=='D'){
                    if(i==point.x-1){
                        flag=false;
                        break;
                    }

                    //왼쪽편으로 이동 시 장애물 만남 + 바로 옆에 장애물이 아닌 경우 왼쪽 이동
                    flag=true;
                    stopX=i+1; //장애물의 위치+1칸으로 이동
                    StringBuilder sb=new StringBuilder(leftBoard[point.y]);
                    leftBoard[point.y]=sb.toString();
                    break;
                }else{
                    //그냥 지나가지는 경우 직전 위치를 X로 변경
                    if(leftBoard[point.y].charAt(i+1)=='G')
                        continue;
                    StringBuilder sb=new StringBuilder(leftBoard[point.y]);
                    sb.setCharAt(i+1,'X');
                    leftBoard[point.y]=sb.toString();
                }
            }
            if(flag){
                //벽 혹은 장애물을 먼저 만난 경우
                possiblePoints.add(new Point(stopX, point.y,leftBoard));
            }
        }

        //R
        if(point.x<board[point.y].length()-1){
            String[] rightBoard=board.clone();
            boolean flag=true;
            //해당 방향으로 가는데 지나온길이 장애물이나 벽 전에 존재하면 break ->false
            //X를 만나지않고 벽 혹은 장애물에 도착하는 경우 ->true
            int stopX=rightBoard[point.y].length()-1;
            for (int i = point.x+1; i <rightBoard[point.y].length(); i++) {
                if(rightBoard[point.y].charAt(i)=='X'){
                    flag=false;
                    break;
                }else if(rightBoard[point.y].charAt(i)=='D'){
                    if(i==point.x+1){
                        flag=false;
                        break;
                    }
                    //왼쪽편으로 이동 시 장애물 만남 + 바로 옆에 장애물이 아닌 경우 왼쪽 이동
                    flag=true;
                    stopX=i-1;
                    break;
                }else{
                    if(rightBoard[point.y].charAt(i-1)=='G')
                        continue;
                    //그냥 지나가지는 경우 X로 변경
                    StringBuilder sb=new StringBuilder(rightBoard[point.y]);
                    sb.setCharAt(i-1,'X');
                    rightBoard[point.y]=sb.toString();
                }
            }
            if(flag){
                //벽 혹은 장애물을 먼저 만난 경우
                possiblePoints.add(new Point(stopX, point.y,rightBoard));
            }
        }

        //U
        if(point.y>0){
            String[] upBoard=board.clone();
            boolean flag=true;
            //해당 방향으로 가는데 지나온길이 장애물이나 벽 전에 존재하면 break ->false
            //X를 만나지않고 벽 혹은 장애물에 도착하는 경우 ->true
            int stopY=0;
            for (int i = point.y-1; i >=0; i--) {
                if(upBoard[i].charAt(point.x)=='X'){
                    flag=false;
                    break;
                }else if(upBoard[i].charAt(point.x)=='D'){
                    if(i==point.y-1){
                        flag=false;
                        break;
                    }
                    //왼쪽편으로 이동 시 장애물 만남 + 바로 옆에 장애물이 아닌 경우 왼쪽 이동
                    flag=true;
                    stopY=i+1; //장애물의 위치+1칸으로 이동
                    break;
                }else{
                    if(upBoard[i+1].charAt(point.x)=='G')
                        continue;
                    //그냥 지나가지는 경우 X로 변경
                    StringBuilder sb=new StringBuilder(upBoard[i+1]);
                    sb.setCharAt(point.x,'X');
                    upBoard[i+1]=sb.toString();
                }
            }
            if(flag){
                //벽 혹은 장애물을 먼저 만난 경우
                possiblePoints.add(new Point(point.x, stopY,upBoard));
            }
        }

        //D
        if(point.y<board.length-1){
            String[] downBoard=board.clone();
            boolean flag=true;
            //해당 방향으로 가는데 지나온길이 장애물이나 벽 전에 존재하면 break ->false
            //X를 만나지않고 벽 혹은 장애물에 도착하는 경우 ->true
            int stopY=downBoard.length-1;
            for (int i = point.y+1; i <downBoard.length; i++) {
                if(downBoard[i].charAt(point.x)=='X'){
                    flag=false;
                    break;
                }else if(downBoard[i].charAt(point.x)=='D'){
                    if(i==point.y+1){
                        flag=false;
                        break;
                    }
                    //왼쪽편으로 이동 시 장애물 만남 + 바로 옆에 장애물이 아닌 경우 왼쪽 이동
                    flag=true;
                    stopY=i-1; //장애물의 위치+1칸으로 이동
                    break;
                }else{
                    if(downBoard[i-1].charAt(point.x)=='G')
                        continue;
                    //그냥 지나가지는 경우 X로 변경
                    StringBuilder sb=new StringBuilder(downBoard[i-1]);
                    sb.setCharAt(point.x,'X');
                    downBoard[i-1]=sb.toString();
                }
            }
            if(flag){
                //벽 혹은 장애물을 먼저 만난 경우
                possiblePoints.add(new Point(point.x, stopY,downBoard));
            }
        }

        return possiblePoints;
    }
}

통과코드

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public static int answer=Integer.MAX_VALUE;
    public static String[] boardPlate;
    public static int[][] tripFlag;
    public int solution(String[] board) {
        boardPlate=board.clone();

        int x = 0,y=0;
        boolean findFlag=false;
        for (int j=0;j<board.length;j++) {
            if(findFlag)
                break;
            for (int i = 0; i < board[j].length(); i++) {
                if(board[j].charAt(i)=='R'){
                    x=i;
                    y=j;
                    //System.out.println("Found :"+x+"/"+y);
                    findFlag=true;
                    break;
                }
            }
        }
        tripFlag=new int[board[0].length()][board.length];
        tripFlag[x][y]=0;
        dfs(0,x,y,board);

        if(answer==Integer.MAX_VALUE)
            return -1;
        return answer;
    }

    public void dfs(int moveCount,int x, int y,String[] board){
        //System.out.println("Now in "+x + " / " +y + " value="+board[y].charAt(x));
        //printBoard(board);
        if(moveCount>answer)
            return;
        if(boardPlate[y].charAt(x)=='G'){
            answer=moveCount;
        }

        if(x>0){
            String originLine=board[y];
            String line= board[y];
            if(line.charAt(x-1)=='.'||line.charAt(x-1)=='G'){
                //바로 왼쪽이 지나온 길이거나 장애물이 있으면 왼쪽으로 가지 못한다.
                int newX=0;
                for (int i = x-1; i >= 0; i--) {
                    if(line.charAt(i)=='D'){
                        newX=i+1;
                        break;
                    }
                }
                //char target = line.charAt(newX);
                if(tripFlag[newX][y]>moveCount+1||tripFlag[newX][y]==0){
                    //방문한 적이 없는 곳이거나 기존 방문보다 더 효율적으로 도착한 경우만 다음 step 진행
                    tripFlag[newX][y]=moveCount+1;
                    dfs(moveCount+1,newX,y,board);
                }

            }

        }
        if(y>0){
            String line="";
            for (int i = 0; i < board.length; i++) {
                line+=board[i].charAt(x);
            }
            if(line.charAt(y-1)=='.'||line.charAt(y-1)=='G'){
                int newY=0;
                for (int i = y-1; i >= 0; i--) {
                    if(line.charAt(i)=='D'){
                        newY=i+1;
                        break;
                    }
                }
                //char target = board[newY].charAt(x);

                if(tripFlag[x][newY]>moveCount+1||tripFlag[x][newY]==0){
                    tripFlag[x][newY]=moveCount+1;
                    dfs(moveCount+1,x,newY,board);
                }
            }
        }
        if(x<board[y].length()-1){
            String originLine=board[y];
            String line= board[y];
            if(line.charAt(x+1)=='.'||line.charAt(x+1)=='G'){
                int newX=board[y].length()-1;
                for (int i = x+1; i < board[y].length(); i++) {
                    if(line.charAt(i)=='D'){
                        newX=i-1;
                        break;
                    }
                }
                if(tripFlag[newX][y]>moveCount+1||tripFlag[newX][y]==0){
                    tripFlag[newX][y]=moveCount+1;
                    dfs(moveCount+1,newX,y,board);
                }

            }
        }
        if(y<board.length-1){
            String line="";
            for (int i = 0; i < board.length; i++) {
                line+=board[i].charAt(x);
            }
            //System.out.println("origin line : "+originLine);
            if(line.charAt(y+1)=='.'||line.charAt(y+1)=='G'){
                int newY=board.length-1;
                boolean flag=true;
                for (int i = y+1; i < board.length; i++) {
                    if(line.charAt(i)=='D'){
                        newY=i-1;
                        break;
                    }
                }
                if(tripFlag[x][newY]>moveCount+1||tripFlag[x][newY]==0){
                    tripFlag[x][newY]=moveCount+1;
                    dfs(moveCount+1,x,newY,board);
                }
            }
        }
    }
    public void printBoard(String[] board){
        System.out.println("================print=========================");
        for (String s : board) {
            System.out.println(s);
        }
        System.out.println("================end===========================");
    }   
}

---

4번정도 틀리고 힘들게 푼 문제..

전형적인 BFS문제인데, 그냥 DFS로 풀었다..

처음엔, 지나온 길을 다시 지나가면 최소 이동 경로가 될 수 없다고 생각하고 지나간 길을 모두 X표시하는 로직을 구현했는데, 생각해보면 문제는 벽이나 장애물에 닿을 떄 까진 쭉 가기에 지나간 길을 다시 지나갈 수 있어야 한다.

그래서,, 코드를 갈아 엎고 지나온 "점"만 기록하는 로직을 구현했었다. (true,false로) 

근데, 난 BFS로 풀었으니 한번 쭉 트리를 돌고 다시 돌아올 떄 이미 지나갔던 길을 다시 false로 바꾸어 지나갈 수 있게 했다.

만약, 첫 탐색 떄 4회만에 도착한 지점을 다음 탐색 땐, 5회만에 도착한다면 그 이후의 몇백 몇천개의 탐색을 하든 첫 탐색과 비교하면 더 먼 거리를 이동해야 한다.

그래서 ! 다시 코드를 수정했다.

지나가지 않았거나 지나갔던 지점이여도 현재 경로가 더 빠르다면 해당 지점의 이동 횟수를 저장하는 방식으로 변경했다.

이렇게 되면, 굳이 이미 더 오래걸릴 것이 확실한 상황에서 탐색을 이어나가지 않는다.

수정 후 제출하니 편안하게 통과했다.

 

아무래도 DFS 문제도 더 풀어봐야 할 것 같다.