[프로그래머스] 리코쳇 로봇 - Java

문제

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

프로그래머스

 

---

 

문제 개요

이 문제는 리코쳇 로봇이라는 보드게임을 기반으로 하고 있습니다. 게임의 목표는 격자 모양의 게임판에서 주어진 위치에 있는 로봇("R")을 특정 목표 위치("G")로 이동시키는 것입니다.

규칙

1. 로봇은 한 번에 상, 하, 좌, 우 방향 중 하나로 움직이며 장애물("D")이나 게임판 가장자리에 닿기 전까지 멈추지 않습니다.
2. "R"에서 "G"로 도달하기 위해 필요한 최소 이동 횟수를 계산합니다.
3. 목표 지점에 도달할 수 없을 경우 -1을 반환합니다.

 

접근 방법

1. 문제 해결 전략

이 문제는 최단 경로를 찾아야 하므로 BFS(너비 우선 탐색) 알고리즘을 사용합니다. BFS는 모든 경로를 동일한 깊이에서 탐색하므로, 목표 지점에 도달하면 그 경로가 최단 경로임이 보장됩니다.

2. 세부 구현

1. 데이터 변환 및 초기화
   • 입력 문자열 배열(board)을 2차원 배열(map)로 변환합니다.
   • visited 배열을 사용하여 이미 방문한 위치를 기록합니다.
2. BFS 탐색
   • 로봇의 시작 위치("R")를 큐에 삽입하고 BFS 탐색을 시작합니다.
   • 큐에서 현재 노드(좌표 및 이동 횟수)를 꺼낸 후, 4방향(상, 하, 좌, 우)으로 이동을 시도합니다.
   • 이동할 수 있는 범위는 장애물("D")이나 가장자리에 부딪힐 때까지 계속됩니다.
   • 이동이 완료된 위치가 이미 방문된 경우 건너뜁니다.
3. 목표 지점 도달 여부
   • BFS 도중 목표 지점("G")에 도달하면 그때의 이동 횟수를 기록하고 탐색을 종료합니다.
   • BFS 탐색이 종료되었음에도 "G"에 도달하지 못했다면 -1을 반환합니다.

import java.util.*;
class Solution {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static String[][] map;
    static int ans = -1;
    static boolean[][] v;
    public int solution(String[] board) {
        int answer = 0;
        map = new String[board.length][board[0].length()];
        v = new boolean[board.length][board[0].length()];
        
        for(int i=0; i<map.length; i++) map[i] = board[i].split("");
        
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(map[i][j].equals("R")) {
                    bfs(new Node(i, j, 0));
                }
            }
        }
        
        return ans;
    }
    
    public void bfs(Node node) {
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        
        while(!q.isEmpty()) {
            Node cur = q.poll();
            v[cur.r][cur.c] = true;
            if(map[cur.r][cur.c].equals("G")) {
                ans = cur.cnt;
                return;
            }
            
            for(int i=0; i<4; i++) {
                int nr = cur.r;
                int nc = cur.c;
                
                while(true) {
                    nr += dr[i];
                    nc += dc[i];
                    if(nr < 0 || nc < 0 || nr>=map.length || nc>=map[0].length || map[nr][nc].equals("D")) break;    
                }
                
                nr -= dr[i];
                nc -= dc[i];
                
                if(v[nr][nc]) continue;
                q.add(new Node(nr, nc, cur.cnt+1));
            }
        }
    }
    
    class Node {
        int r, c, cnt;
        public Node(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}