[JAVA] 프로그래머스 리코쳇 로봇

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(String[] board) {
        int[] goal = new int[2];
        int[] start = new int[2];
        Queue<int[]> nextNode = new LinkedList<>();
        boolean[][] visited = new boolean[board.length][board[0].length()];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length(); j++) {
                if (board[i].charAt(j) == 'R') {
                    start[0] = i;
                    start[1] = j;
                }
                if (board[i].charAt(j) == 'G') {
                    goal[0] = i;
                    goal[1] = j;
                }
            }
        }


        nextNode.add(start);
        visited[start[0]][start[1]] = true;
        int moveCount = 0;

        // BFS
        while (!nextNode.isEmpty()) {
            int size = nextNode.size();
            moveCount++;

            for (int i = 0; i < size; i++) {
                int[] currNode = nextNode.poll();

                for (int[] direction : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
                    int[] newPos = movePosition(board, currNode, direction[0], direction[1]);

                    if (newPos[0] == goal[0] && newPos[1] == goal[1]) {
                        return moveCount;
                    }

                    if (!visited[newPos[0]][newPos[1]]) {
                        visited[newPos[0]][newPos[1]] = true;
                        nextNode.add(newPos);
                    }
                }
            }
        }

        return -1; // 도착하지 못한 경우
    }

    public int[] movePosition(String[] board, int[] pos, int x, int y) {
        int nextX = pos[0];
        int nextY = pos[1];

        while (true) {
            int newX = nextX + x;
            int newY = nextY + y;

            if (newX < 0 || newX >= board.length ||
                newY < 0 || newY >= board[0].length() || board[newX].charAt(newY) == 'D') {
                break;
            }

            nextX = newX;
            nextY = newY;
        }

        return new int[]{nextX, nextY};
    }
}

 

풀이

1. 한 방향으로만 전진해서 배열의 끝이나 'D'에 도착했을 때의 위치를 반환하는 메서드를 만든다.

2. 해당 메서드를 가지고 bfs를 하게되는데 queue에 저장된 각 위치에서 상하좌우를 검색한다.

3. 방문한 곳은 다음 queue에 넣지 않는다.

4. goal 위치에 도착했다면 몇번 반복했는지 반환해주고 queue를 다 이동할 동안 찾지 못했다면 -1을 반환한다.

 

 

느낀점

코딩테스트로 java를 익히는 중인데 코딩테스트로 연습하면서 하니까 오래걸리긴하나 모르던 점들을 알게 되었다. String은 c++에서의 const와 비슷한 성질을 지닌 값이였다. String내용을 수정 불가하다는 것은 const와 같았으나 java에서의 경우 String객체를 새로 대입해주는 것은 가능했다.

 

 

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

프로그래머스