프로그래머스 - 리코쳇 게임(Java)

By on January 23, 2024

프로그래머스 - 리코쳇 게임(Java)

문제 링크 : 리코쳇 게임

리코쳇 게임 이란?

리코쳇 게임은 1999년에 Alex Randolph가 디자인 한 추상 전략 보드 게임 입니다.
격자 모양의 보드에 로봇이 있는데 해당 로봇은 한 방향으로 이동 할 수 있으며 한번 이동 하면 벽을 만날때 까지 가야 합니다.

문제 해결 접근법(BFS 응용)

문제를 해결하기 위한 접근 방법은 다음과 같습니다.

  • 위치를 저장 할 수 있는 Position 객체를 생성한다.
  • 최초 시작 지점(‘R’)을 찾는다. getStartPosition();
  • bfs() 로 탐색 하면서 종료 지점(‘G’) 를 찾아서 이동 횟수(Position.moveCnt)를 리턴 한다.
  • 종료 지점을 찾을 수 없다면 -1 을 리턴 한다.

소스

public class 리코쳇게임 {

    @Test
    void 리코쳇게임_테스트(){
        Assertions.assertThat(solution(new String[]{"...D..R", ".D.G...", "....D.D", "D....D.", "..D...."})).isEqualTo(7);
        Assertions.assertThat(solution(new String[]{".D.R", "....", ".G..", "...D"})).isEqualTo(-1);
    }

    private static final String START = "R";
    private static final String GOAL = "G";
    private static final String SPACE = ".";
    private static final String WALL = "D";

    private static final int[] POS_X = {0, 0, -1, 1};
    private static final int[] POS_Y = {-1, 1, 0, 0};

    public int solution(String[] board) {
        int answer = 0;
        Position startPosition = getStartPosition(board);
        answer = bfs(startPosition, board);
        return answer;
    }

    /**
     * 시작 지점 탐색
     * @param  board 게임 맵
     * @return 시작 지점 Position
     */
    private Position getStartPosition(String[] board) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].getBytes().length; j++) {
                if(START.equals(String.valueOf(board[i].charAt(j)))){
                    return new Position(i, j, 0);
                }
            }
        }
        return null;
    }

    /**
     * 리코쳇 게임 시작
     * @param startPosition 시작 지점
     * @param board 게임 맵
     * @return 이동 횟수
     */
    private static int bfs(Position startPosition, String[] board) {
        Queue<Position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[board.length + 1][board[0].getBytes().length + 1];

        queue.add(startPosition);
        visited[startPosition.x][startPosition.y] = true;

        while (!queue.isEmpty()){
            Position nowPosition = queue.poll();

            //현재 위치가 GOAL 이면 종료 한다.
            if(GOAL.equals(String.valueOf(board[nowPosition.x].charAt(nowPosition.y)))){
                System.out.println("GOAL : " + nowPosition);
                return nowPosition.moveCnt;
            }

            //동서남북으로 돌면서 위치를 이동 하여 해당 되는 커서 위치를 큐에 담는다.
            for(int i = 0; i < 4; i++){
                int cur_x = nowPosition.x;
                int cur_y = nowPosition.y;

                //한쪽 방향을 선택 했다면 벽을 만나 거나 갈 수 없을때 까지 커서를 이동 시킨다.
                while(cur_x + POS_X[i] >= 0 && cur_x + POS_X[i] < board.length
                        && cur_y + POS_Y[i] >= 0 && cur_y + POS_Y[i] < board[0].getBytes().length
                        && !WALL.equals(String.valueOf(board[cur_x + POS_X[i]].charAt(cur_y + POS_Y[i])))){
                    cur_x += POS_X[i];
                    cur_y += POS_Y[i];
                }
                
                //방문한 적이 없는 위치 라면 큐에 담는다.
                if(!visited[cur_x][cur_y]){
                    visited[cur_x][cur_y] = true;
                    queue.offer(new Position(cur_x, cur_y, nowPosition.moveCnt+1));
                }
            }
        }
        return -1;
    }

    static class Position{
        int x;
        int y;
        int moveCnt;
        public Position(int x, int y, int moveCnt) {
            this.x = x;
            this.y = y;
            this.moveCnt = moveCnt;
        }

        @Override
        public String toString() {
            return "Position{" +
                    "x=" + x +
                    ", y=" + y +
                    ", moveCnt=" + moveCnt +
                    '}';
        }
    }
}

Back to blog