[JAVA 문제 풀이] 379. 리코쳇 로봇

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(String[] board) {
        int n = board.length; // 행 수
        int m = board[0].length(); // 열 수
        char[][] map = new char[n][m]; // 문자형 맵
        int startX = 0;
        int startY = 0;
        
        // 맵 초기화 및 시작점 위치 찾기
        for (int i = 0; i < n; i++) {
            map[i] = board[i].toCharArray();
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'R') {
                    startX = i;
                    startY = j;
                }
            }
        }
        
        // BFS 호출
        return bfs(map, startX, startY, n, m);
    }
    
    // 최소 이동 횟수 반환 BFS
    private int bfs(char[][] map, int startX, int startY, int n, int m) {
        // 상하좌우
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };
        Queue<int[]> q = new LinkedList<>(); // 위치와 이동 횟수를 저장할 큐
        boolean[][] visited = new boolean[n][m]; // 방문 여부 체크

        q.offer(new int[] { startX, startY, 0 }); // x, y, 이동 횟수

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            int moves = cur[2];

            if (map[x][y] == 'G')
                return moves;

            // 이미 방문한 칸이면 패스
            if (visited[x][y])
                continue;
            visited[x][y] = true;

            // 4방향으로 미끄러지기
            for (int d = 0; d < 4; d++) {
                int nx = x;
                int ny = y;

                // 장애물이나 벽에 닿을 때까지 이동
                while (true) {
                    int tx = nx + dx[d];
                    int ty = ny + dy[d];

                    // 범위 밖 or 장애물에 닿으면 중지
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m || map[tx][ty] == 'D')
                        break;

                    nx = tx;
                    ny = ty;
                }

                // 아직 방문하지 않은 칸만 큐에 추가
                if (!visited[nx][ny]) {
                    q.offer(new int[] { nx, ny, moves + 1 });
                }
            }
        }

        return -1; // 목표 지점 도달 불가
    }
}

다른 사람의 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(String[] board) {
        return new Board(board).calculateMoveCount();
    }

    // 보드(Board) 클래스
    // 보드의 각 위치에 있는 토큰(Token)들을 관리하고, 로봇이 목표 지점까지 이동하는 최소 횟수를 계산
    private static class Board {
        private static final int[] DY = { 1, -1, 0, 0 };
        private static final int[] DX = { 0, 0, 1, -1 };
        private final List<List<Token>> board;

        public Board(String[] board) {
            // board 배열의 각 행(i)과 각 열(j)에 대해
            // Token 객체를 생성하여 2차원 리스트(List<List<Token>>)로 변환
            this(IntStream.range(0, board.length)
                    .mapToObj(i -> IntStream.range(0, board[i].length())
                            .mapToObj(j -> new Token(Point.of(j, i),
                                    TokenType.findType(Character.toString(board[i].charAt(j)))))
                            .collect(Collectors.toList()))
                    .collect(Collectors.toList()));
        }

        public Board(List<List<Token>> board) {
            this.board = board;
        }

        // 로봇이 목표 지점까지 이동하는 최소 횟수를 계산하는 메서드
        public int calculateMoveCount() {
            Token start = board.stream()
                    .flatMap(Collection::stream) // 2차원 리스트를 1차원 스트림으로 펼침
                    .filter(token -> token.getTokenType().isRobot()) // 토큰 타입이 로봇인 것만 필터링
                    .findAny() // 첫 번째 로봇 토큰을 찾음
                    .orElseThrow(); // 없으면 예외 발생

            Token end = board.stream()
                    .flatMap(Collection::stream)
                    .filter(token -> token.getTokenType().isGoal())
                    .findAny()
                    .orElseThrow();

            return calculateMoveCount(start, end);
        }

        // 시작 토큰에서 목표 토큰까지 이동하는 최소 횟수를 계산하는 메서드
        private int calculateMoveCount(Token start, Token end) {
            int maxY = board.size(); // 보드의 행 수
            int maxX = board.get(0).size(); // 보드의 열 수

            boolean[][] visited = new boolean[maxY][maxX]; // 방문 여부를 기록하는 2차원 배열
            Queue<Token> tokens = new LinkedList<>(); // BFS를 위한 큐
            int count = Integer.MAX_VALUE; // 최소 이동 횟수를 저장

            tokens.add(start); // 시작 토큰을 큐에 추가
            visited[start.getPoint().getY()][start.getPoint().getX()] = true; // 시작 위치를 방문 처리

            // 탐색 시작
            while (!tokens.isEmpty()) {
                Token current = tokens.poll();
                Point currentPoint = current.getPoint();

                // 현재 위치가 목표 위치와 같으면 최소 이동 횟수를 업데이트
                if (current.equals(end)) {
                    count = Integer.min(count, current.getCount());
                }

                // 현재 위치에서 상하좌우로 이동 가능한 모든 위치를 탐색
                for (int i = 0; i < 4; i++) {
                    int dx = DX[i];
                    int dy = DY[i];
                    Point nextPoint = currentPoint;

                    // 현재 위치에서 dx, dy 방향으로 이동 가능한 최대 위치를 찾음
                    while (nextPoint.increasable(dx, dy, 0, 0, maxX - 1, maxY - 1) &&
                            board.get(nextPoint.getY() + dy).get(nextPoint.getX() + dx).getTokenType().movable()) {
                        nextPoint = nextPoint.increase(dx, dy);
                    }

                    // 다음 위치가 방문하지 않은 곳이면
                    // 해당 위치의 토큰을 업데이트하고 큐에 추가
                    if (!visited[nextPoint.getY()][nextPoint.getX()]) {
                        Token token = board.get(nextPoint.getY()).get(nextPoint.getX());
                        token.updateCount(current.getCount() + 1);
                        tokens.add(token);
                        visited[nextPoint.getY()][nextPoint.getX()] = true;
                    }
                }
            }

            // 모든 탐색이 끝난 후, 최소 이동 횟수를 반환
            return Integer.MAX_VALUE == count ? -1 : count;
        }
    }

    // 토큰(Token) 클래스
    // 각 위치에 있는 토큰의 정보를 저장
    private static class Token {
        private final Point point;
        private final TokenType tokenType;
        private int count;

        public Token(Point point, TokenType tokenType) {
            this.point = point;
            this.tokenType = tokenType;
            this.count = 0;
        }

        public int getCount() {
            return count;
        }

        // 토큰의 이동 횟수를 업데이트하는 메서드
        public void updateCount(int count) {
            this.count = count;
        }

        public Point getPoint() {
            return point;
        }

        public TokenType getTokenType() {
            return tokenType;
        }
    }

    // 토큰 타입(TokenType) 열거형
    // 각 토큰의 종류를 정의
    private enum TokenType {
        ROBOT("R"),
        GOAL("G"),
        OBSTACLE("D"),
        EMPTY(".");

        private final String type;

        TokenType(String type) {
            this.type = type;
        }

        // 주어진 문자열에 해당하는 토큰 타입을 찾는 메서드
        public static TokenType findType(String type) {
            return Arrays.stream(values())
                    .filter(token -> token.type.equals(type))
                    .findAny()
                    .orElseThrow();
        }

        // 토큰 타입에 따라 로봇, 목표, 장애물, 빈 공간 여부를 확인하는 메서드
        public boolean isRobot() {
            return ROBOT.equals(this);
        }

        public boolean isGoal() {
            return GOAL.equals(this);
        }

        public boolean isObstacle() {
            return OBSTACLE.equals(this);
        }

        public boolean isEmpty() {
            return EMPTY.equals(this);
        }

        // 토큰이 이동 가능한지 확인하는 메서드
        public boolean movable() {
            return !isObstacle();
        }
    }

    // 포인트(Point) 클래스
    // 2차원 좌표를 나타내며, 캐시를 사용하여 중복 객체 생성을 방지
    private static class Point {
        private static final Point[][] CACHE = new Point[101][101]; // 문제 제한 사항에 따른 최대값
        private final int x;
        private final int y;

        private Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        // 캐시를 사용하여 중복된 Point 객체 생성을 방지
        public static Point of(int x, int y) {
            if (Objects.isNull(CACHE[y][x])) {
                Point point = new Point(x, y);
                CACHE[y][x] = point;
            }

            return CACHE[y][x];
        }

        // Point 객체의 x, y 좌표를 증가시킨 새로운 Point 객체를 반환
        public Point increase(int x, int y) {
            return Point.of(this.x + x, this.y + y);
        }

        // 주어진 범위 내에서 x, y 좌표를 증가시킬 수 있는지 확인
        public boolean increasable(int x, int y, int minX, int minY, int maxX, int maxY) {
            return this.x + x >= minX && this.x + x <= maxX &&
                    this.y + y >= minY && this.y + y <= maxY;
        }

        // 현재 Point가 주어진 범위 내에 있는지 확인
        public boolean isIn(int minX, int minY, int maxX, int maxY) {
            return this.x >= minX && this.x <= maxX &&
                    this.y >= minY && this.y <= maxY;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}