[prog 169199] 리코쳇 로봇

프로그래머스

 

import java.util.*;

class Solution {
    static char[][] map;
    static boolean[][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int startR, startC;
    
    static class Point {
        int r, c, cnt;
        
        Point(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
    
    public int solution(String[] board) {
        map = new char[board.length][board[0].length()];
        visited = new boolean[board.length][board[0].length()];
        
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length(); c++) {
                map[r][c] = board[r].charAt(c);
                
                if (map[r][c] == 'R') {
                    startR = r;
                    startC = c;
                }
            }
        }
        return dfs();
    }
    
    static int dfs() {
        Queue<Point> q = new LinkedList<>();
        
        // 1. 시작점 넣고 방문 처리
        q.offer(new Point(startR, startC, 0));
        visited[startR][startC] = true;
        
        while (!q.isEmpty()) {
            Point p = q.poll();
            
            // 2. 도착시 BFS 종료
            if(map[p.r][p.c] == 'G')  return p.cnt;
            
            for (int i = 0; i < 4; i++) {
                int nr = p.r;
                int nc = p.c;
                
                // nr, nc에 "해당 방향으로 끝까지 이동한 좌표"를 저장하기
                while (true) {
                    int rr = nr + dr[i];
                    int cc = nc + dc[i];
                    
                    if (!inMap(rr, cc) || map[rr][cc] == 'D')  break;
                    
                    nr = rr;
                    nc = cc;
                }
                
                if (!visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.add(new Point(nr, nc, p.cnt + 1));
                }
            }
        }
        return -1;
    }
    
    static boolean inMap(int r, int c) {
        return 0 <= r && r < map.length && 0 <= c && c < map[0].length;
    }
}

 

1. 문제 요약

• 이 문제는 "리코쳇 로봇"이라는 보드게임을 모델링한 것으로, 로봇이 격자 모양의 게임판 위에서 시작 위치에서 목표 위치까지 최소 몇 번 이동해야 도달할 수 있는지를 찾는 문제입니다.
• 로봇은 상하좌우 방향으로 이동하며, 장애물이나 보드의 끝에 부딪힐 때까지 계속 움직입니다.
• 목표 위치에 도달할 수 없는 경우 -1을 반환합니다.

 

2. 핵심 아이디어

1. BFS(너비 우선 탐색) 사용:
   • BFS는 최단 경로를 찾는 데 적합한 알고리즘입니다. 큐를 사용하여 현재 위치와 이동 횟수를 저장합니다.
   • BFS를 사용하여 각 위치에서 상하좌우 네 방향으로 장애물이나 맵 끝에 도달할 때까지 이동합니다.
2. 이동 범위 계산:
   • 각 방향으로 이동할 때, 장애물이나 맵 끝에 도달할 때까지 계속 이동합니다.
   • 도달한 위치가 아직 방문되지 않은 경우, 방문 처리를 하고 큐에 추가하여 탐색을 계속합니다.
3. 경계 및 조건 체크:
   • 이동할 위치가 맵의 범위를 벗어나지 않는지 확인하고, 장애물에 부딪혔는지 확인합니다.
   • 목표 위치에 도달한 경우, 현재까지의 이동 횟수를 반환합니다.

 

3. 출제 의도

1. 최단 경로 탐색 알고리즘 이해 및 구현 능력 평가:
   • BFS를 사용하여 최단 경로를 찾는 문제 해결 능력을 평가합니다.
2. 2차원 배열 및 경계 조건 처리 능력 평가:
   • 2차원 배열을 다루는 능력과 경계 조건을 정확히 처리하는 능력을 평가합니다.
3. 문제 분석 및 구현 능력 평가:
   • 문제의 요구 사항을 분석하고, 이를 구현하는 능력을 평가합니다. 특히, 장애물 처리와 같은 조건을 정확히 구현하는 능력을 테스트합니다.