99클럽 코테 스터디 33일차 TIL - [프로그래머스] 리코쳇 로봇 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 리코쳇 로봇 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/169199

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 게임판의 상태를 나타내는 문자열 배열 board
출력 : 말이 목표위치에 도달하는데 이동해야하는 최소 거리. 단, 목표 위치에 도달할 수 없다면 -1 리턴

가능한 시간복잡도

O(n)

알고리즘 선택

bfs

📌 코드 설계하기

1. 주어진 보드에서 시작점('R')과 목표점('G')의 위치를 탐색하고, 각각의 위치를 start와 goal 변수에 저장한다.
2. BFS를 위한 큐를 생성하고, 시작점을 큐에 추가한다. 방문 배열(visited)을 만들어 이미 방문한 위치를 기록한다.
3. 큐에서 현재 위치를 꺼내고, 목표점에 도달했는지 확인한다.
4. 네 방향(위, 아래, 왼쪽, 오른쪽)으로 이동하면서 장애물('D')이나 보드의 경계에 도달할 때까지 계속 이동한다.
5. 새로운 위치를 찾으면 큐에 추가하고, 방문 배열을 업데이트한다.
6. 목표점에 도달하면 이동 횟수를 반환하고, 도달할 수 없다면 -1을 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    private int[] dx = {0, 0, -1, 1}; // Direction vectors for row movement
    private int[] dy = {-1, 1, 0, 0}; // Direction vectors for column movement

    static class Point {
        int x, y, depth;
        Point(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }

    public int solution(String[] board) {
        int n = board.length;
        int m = board[0].length();
        boolean[][] visited = new boolean[n][m];
        
        Queue<Point> queue = new LinkedList<>();
        Point start = null, goal = null;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i].charAt(j) == 'R') {
                    start = new Point(i, j, 0);
                }
                if (board[i].charAt(j) == 'G') {
                    goal = new Point(i, j, 0);
                }
            }
        }
        
        queue.add(start);
        visited[start.x][start.y] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();
            
            if (current.x == goal.x && current.y == goal.y) {
                return current.depth;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = current.x;
                int ny = current.y;
                
                while (nx + dx[i] >= 0 && nx + dx[i] < n && ny + dy[i] >= 0 && ny + dy[i] < m
                        && board[nx + dx[i]].charAt(ny + dy[i]) != 'D') {
                    nx += dx[i];
                    ny += dy[i];
                }
                
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new Point(nx, ny, current.depth + 1));
                }
            }
        }

        return -1;
    }
}