[Programmers] 리코쳇 로봇 (JAVA)

프로그래머스

 

풀이

 

구현+BFS 문제 .. 나는 참 구현문제가 힘들다🥹

일단 이번 문제를 풀 때 내가 간과한 부분이 있다면 큐의 작동원리인 것 같다.

 

처음 문제를 보고 전체를 방문하면서 큐에 넣고 빼면서 하나하나 체크를 해줬는데, 그렇게 풀었더니 테케 1, 7, 9, 25에서 실패가 나왔다.

생각해보니 그렇게 문제를 해결하다보면, 더 짧게 방문할 수 있는 분기B가 있는데도 이미 이전 A가 방문하고 지나쳐버렸기 때문에 더 짧게 도달하지 못하는 경우가 생긴다.

 

그리고, 끝까지 하나하나 체크하면서 너 끝이니? 너 장애물이니? 체크해주면 터지지 않을까 했는데,

최대 100x100이기도 하고, 중간중간 장애물이 있기 때문에 while문을 돌면서 벽에 부딪치거나 map밖으로 나가면!

이전 위치의 visited[n.x][n.y]에 저장해놓은 내가 이동한 횟수에 +1을 해줘서 문제를 풀었다.

 

한번 꼬여서 고생했지만 풀고나니까 굉장히 후련한 문제 ~!

구현 문제를 열심히 더 풀어보자 !

 

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    //상좌하우 0 1 2 3
    static int goX[] = {-1, 0, 1, 0};
    static int goY[] = {0, -1, 0, 1};
    static int N;
    static int M;
    static int visited[][];
    static char map[][];
    static int ans;
    static boolean row[];
    static class Node{
        int x;
        int y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int solution(String[] board) {
        map = new char[board.length][board[0].length()];
        for(int i=0; i<board.length; i++){
            map[i] = board[i].toCharArray();
        }
        N = board.length;
        M = map[0].length;
        visited = new int[N][M];
        row = new boolean[4];
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j] == 'R'){
                    Robot(i, j);
                    break;
                }
            }
        }
        
        if(ans == 0){
            ans = -1;
        }
        return ans;
    }
    static void Robot(int x, int y){
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x, y));
        visited[x][y] = 1;
        
        while(!queue.isEmpty()){
            Node n = queue.poll();
            
            int newX = n.x;
            int newY = n.y;
            
            //n의 가야하는 방향을 지정
            for(int i=0; i<4; i++){
                int nX = newX + goX[i];
                int nY = newY + goY[i]; 

                if(nX < 0 || nX >= N || nY < 0 || nY >= M || map[nX][nY] == 'D'){
                    if(row[i]){
                        row[i] = false;
                    }
                    continue;
                }
                
                row[i] = true; 
            }
            
            for(int i=0; i<4; i++){
                int nX = newX;
                int nY = newY;
                if(row[i]){
                    while(true){
                        nX += goX[i];
                        nY += goY[i];

                        //다음이 밖으로 나갔을 때, 벽에 부딪혔을 때는 멈춰!
                        if(nX < 0 || nX >= N || nY < 0 || nY >= M 
                           || map[nX][nY] == 'D'){
                            nX -= goX[i];
                            nY -= goY[i];
                            break;
                        }
                    }

                    //도착지네?
                    if(map[nX][nY] == 'G'){
                        visited[nX][nY] = visited[newX][newY] + 1;
                        ans = visited[nX][nY]-1;
                        return;
                    }
                    
                    if(visited[nX][nY] != 0){
                        continue;
                    }
                    
                    visited[nX][nY] = visited[newX][newY]+1;
                    queue.offer(new Node(nX, nY));
                }else{
                    continue;
                }
            }
        }
    }
}