본문 바로가기
코딩테스트/BFS & DFS

[BFS] 리코쳇 로봇

by asdft 2024. 3. 7.

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 요약

간단히 요약하자면, 처음 위치 R에서 목표 지점 G까지 최소 움직임을 구하는 문제다. 단 이동 할 때 한 칸씩 이동하는 게 아니라 장애물 D 이거나 board 보드를 벗어나기 전까지 멈추지 않고 쭈욱 이동한다고 보면 된다.

이때 G까지 가는 최소 움직임을 return 해주면 된다.

해설

우선, 최소 이동거리를 보장해야 하기 때문에, 너비 우선 탐색(BFS)을 사용하면 효율적이다.

이전 게시글인 미로탈출과 굉장히 유사하고 한가지 다른점은 여기서는 쭉 미끄러져서 이동하는것을 while문을 통해서 구현해주는 것이다.

해당 문제는 미로탈출 문제에서 목적지 까지 최소 움직임을 알기 위한 탐색 문제에서 한 가지만 수정하면 되는 문제이다.

 

 

미끄러져 이동하는 부분의 코드를 한번 살펴보다

  for(int i=0;i<4;i++){ // 상,하,좌,우 모든 방향 탐색 위해 4번반복
                
                int x = cur.x + X[i];   // 방향을 정해주고
                int y = cur.y + Y[i];   // 방향을 정해주고
                
                while(x>=0 && 
                      y>=0 && 
                      x<board.length && 
                      y<board[0].length() && 
                      board[x].charAt(y) != 'D'){
                    x += X[i];
                    y += Y[i];
                }
                
                x -= X[i];  //위의 코드로 현재위치와 'D'가 겹쳐져 있는 상태이므로 한칸 전으로 이동
                y -= Y[i];
                
                if(visited[x][y]){  // 만약 방문처리 되어있는 경우 continue
                    continue;
                }
                
                visited[x][y] = true; // 방문처리 되어있지 않은 경우 true로 방문처리 해주고

 

처음에 방향을 정해주고, while문을 사용해서 끝까지 이동해 주면 x, y 위치가 D이거나 board를 벗어나게 되면 while문에서 나오게 됩니다. 

 

그 후에 x, y를 한번만 빼주게 되면 딱 장애물 전, board 벗어나기 전으로 돌아가게 됩니다.

 

 

전체코드

import java.util.*;
class Solution {
    int[] X = {0,0,-1,1};
    int[] Y = {1,-1,0,0};
    private int[] findPosition(char find, String[] board){
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length();j++){
                if(board[i].charAt(j) == find){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
    public int solution(String[] board) {
        int start[] = findPosition('R',board);  // start[0] : 'R'의 x좌표, start[1] : 'R'의 y좌표 
        
        int count = bfs('G', start, board);
        return count;
    }
    
    private int bfs(char find, int[] start, String[]board){
        int answer = Integer.MAX_VALUE;

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(start[0], start[1], 0));
        
        boolean[][] visited = new boolean[board.length][board[0].length()];
        visited[start[0]][start[1]] = true;         // Queue에서 꺼내온 좌표 방문 처리
        
        while(!q.isEmpty()){
            Node cur = q.poll();
            
            if(answer <= cur.count){    // 지금까지 최소값만 저장되어있는 answer값보다 count가 크면 최소값 조건에 만족하지 않으므로 skip
                continue;
            }
            
            if(board[cur.x].charAt(cur.y) == find){	// char find = 'G'
                answer = Math.min(answer, cur.count);
            }
            
            for(int i=0;i<4;i++){ 
                
                int x = cur.x + X[i];   // 방향을 정해주고
                int y = cur.y + Y[i];   // 방향을 정해주고
                
                while(x>=0 && 
                      y>=0 && 
                      x<board.length && 
                      y<board[0].length() && 
                      board[x].charAt(y) != 'D'){
                      
                    x += X[i];
                    y += Y[i];
                }
                
                x -= X[i];  //위의 코드로 현재위치와 'D'가 겹쳐져 있는 상태이므로 한칸 전으로 이동
                y -= Y[i];
                if(visited[x][y]){  // 만약 방문처리 되어있는 경우 continue
                    continue;
                }
                
                visited[x][y] = true; // 방문처리 되어있지 않은 경우 true로 방문처리 해주고
                
                q.offer(new Node(x, y, cur.count+1));  // 위의 while문 반복
            }
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}
class Node{
    int x;
    int y;
    int count;
    public Node(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }
}

'코딩테스트 > BFS & DFS' 카테고리의 다른 글

[BFS] 미로 탈출 Lv.2  (0) 2024.03.06
[DFS] 광물캐기  (0) 2024.02.29
[BFS] 전력망을 둘로 나누기  (0) 2024.02.20
DFS / BFS  (1) 2024.01.22