[pg] 프로그래머스 리코챗 로봇

1. 문제정의

 리코쳇 로봇이라는 보드게임이라고 하는데, 사실 포켓몬스터 게임에서 빙판에서 벽에 닿을때까지 미끌어지면서 상하좌우 움직이며 내가 가고싶은 최종 위치를 찾는 것이 연상되는 문제이다.

벽은 D , 목표는 G이다. G로 가는 최소한의 움직임을 구하는 것이 문제.

출처: https://siame2ch.tistory.com/564



2. 내가 한 시도

 일단 길찾기이니 bfs로직으로 풀기로 결정했다. bfs로 벽에 닿을 때 까지 진행하면서 벽에 닿으면 해당 위치가 G인지 확인하는 로직으로 구성되어 있다.

3. 코드

import java.util.*;
/**
 * <p>
 * 프로그래머스 LV2
 * 리코쳇 로봇
 * 접근 방법: 각각 up, down, left, right를 큐에 담아가면서 전진하면서 해결.
 */
public class Solution {

    public int solution(String[] board) {
        /*
         * 최소거리인 것 먼저 큐로 꺼내서 작업
         */
        PriorityQueue<Robot> queue = new PriorityQueue<>(Comparator.comparingInt(Robot::getMoveCount));

        /*
         * X,Y 최대좌표
         */
        int X = board.length;
        int Y = board[0].length();

        /*
         * 돌아다닐 맵
         */
        char[][] map = new char[X][Y];

        /*
         * 방문한 곳 체크용 무한루프 방지
         */
        boolean[][] visited = new boolean[X][Y];


        /*
         * map에 데이터 채우고 시작점을 큐에 넣는다.
         */
        for (int i = 0; i < board.length; i++) {
            map[i] = board[i].toCharArray();
            for (int j = 0; j < map[i].length; j++) {
                char c = map[i][j];
                if (c == 'R') {
                    queue.offer(new Robot(i, j, 0));
                    break;
                }
            }
        }

        /*
         * 전진하면서 D일경우 멈추고, 다시 방향 설정, 현재자리가 G 좌표인지 확인
         */
        while (!queue.isEmpty()) {
            Robot poll = queue.poll();

            //up
            int x = poll.getX();
            int y = poll.getY();
            if (map[x][y] == 'G') return poll.getMoveCount();
            while (x > 0) {
                x--;
                if (map[x][y] == 'D') {
                    x++;
                    break;
                }
            }
            if (visited[x][y] != true) {
                queue.offer(new Robot(x, y, poll.getMoveCount()+1));
                visited[x][y] = true;
            }

            //down
            x = poll.getX();
            y = poll.getY();
            while (x < board.length-1) {
                x++;
                if (map[x][y] == 'D') {
                    x--;
                    break;
                }
            }
            if (visited[x][y] != true) {
                queue.offer(new Robot(x, y, poll.getMoveCount()+1));
                visited[x][y] = true;
            }

            //left
            x = poll.getX();
            y = poll.getY();
            while (y > 0) {
                y--;
                if (map[x][y] == 'D') {
                    y++;
                    break;
                }
            }
            if (visited[x][y] != true) {
                queue.offer(new Robot(x, y, poll.getMoveCount()+1));
                visited[x][y] = true;
            }


            //right
            x = poll.getX();
            y = poll.getY();
            while (y < board[0].length()-1) {
                y++;
                if (map[x][y] == 'D') {
                    y--;
                    break;
                }
            }
            if (visited[x][y] != true) {
                queue.offer(new Robot(x, y, poll.getMoveCount()+1));
                visited[x][y] = true;
            }

        }

        return -1;
    }

    class Robot {
        private int x;
        private int y;
        private int moveCount;

        public Robot(int x, int y, int moveCount) {
            this.x = x;
            this.y = y;
            this.moveCount = moveCount;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getMoveCount() {
            return moveCount;
        }
    }
}

4. 회고

 다른 사람들의 풀이를 보니 BFS를 더 짧은 코드로 짠 사람들이 많았다. 다음 번에는 코드 스타일을 참조해서 bfs를 짜 봐야 겠다.

 

 

참조

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

https://siame2ch.tistory.com/564