[ Programmers - LV2 ] 리코쳇 로봇

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

프로그래머스

문제를 잘 읽고, 이해하고, 충분히 생각한 후 풀어야 한다고 매번 반성하지만 또 반성하게 만들어준 문제...

로직 변경으로 여러번 하는 고충을 경험한 후 통과할 수 있었다...

 

주어진 조건들이 명확해서 잘 지키기만 하면 통과까지는 문제가 없는데, 아무래도 그래프 문제를 자주 접하다 보니까 자만하고 문제의 설명보다 나를 믿고 풀었다. (도대체 뭘 믿은거지....)

 

꿈보다 해몽이라고 문제는 뒤로하고 내 상상으로 문제를 풀었다는게 맞는거 같다 ㅎ..

---

[ 📌 분석 ]

나는 처음에 문제를 이해하지 못했던게 단순히 최단거리 탐색이라고만 생각해서 조금 버벅였다.

• 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동
  • 선택한 방향으로 이동 못 할 때까지 이동 해야한다.
• "G" 위치에 멈춰 설 수 있으며
  • "G(Goal)" 을 지나치면 안되고 해당 위치에 멈춰 서야한다.
• "R"과 "G"는 한 번씩 등장합니다.
  • 출발점과 시작점은 하나

알고리즘 문제 풀이는 당연히 모든 조건을 만족해야 하기 때문에 잘못된 해석이 오답으로 이루어진다.

---

[ 📌 부분 코드 - Java ]

⚙️ 선언부

• graph: 주어진 자료구조가 너무 불편해서 편의를 위해서 변경 했습니다.
• visited: 2 차원 배열까지는 설명이 필요 없겠지만, 3 차원 배열의 4의 의미는 4 방향입니다.

N = board.length;
M = board[0].length();
Queue<Point> queue = new LinkedList<>();
boolean[][][] visited = new boolean[N][M][4];  // x, y, 방향
String[][] graph = Arrays.stream(board)
                         .map(str -> str.split(""))
                         .toArray(String[][]::new);

 

 

한 좌표에 대해서 4 방향으로 접근할 수 있기 때문에 4 방향에 대한 접근 체크를 해줬습니다.

최단 거리를 구하는 문제이기 때문에 같은 방향으로 또 지나간다면 체크할 필요 없음

 

⚙️ 한 방향으로 계속 이동

while(isValid(board, nextX, nextY) && !BLOCK.equals(graph[nextX][nextY])) {
    visited[nextX][nextY][i] = true;
    nextX += dx[i];
    nextY += dy[i];
}

 

 

다음 이동 좌표가 더 이상 유효하지 않을 때 까지 이동해주면서 방문 체크까지 해줬습니다.

---

[ 📌 전체 코드 - Java ]

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

class Solution {

    final int[] dx = {-1, 1, 0, 0};
    final int[] dy = {0, 0, -1, 1};

    final String GOAL = "G";
    final String BLOCK = "D";

    int N;
    int M;

    public int solution(String[] board) throws Exception {
        N = board.length;
        M = board[0].length();
        Queue<Point> queue = new LinkedList<>();
        boolean[][][] visited = new boolean[N][M][4];
        String[][] graph = Arrays.stream(board)
                                 .map(str -> str.split(""))
                                 .toArray(String[][]::new);

        queue.add(getStartPoint(board));

        while(!queue.isEmpty()) {
            Point curP = queue.poll();

            for(int i = 0; i < 4; i++) {
                int nextX = curP.x + dx[i];
                int nextY = curP.y + dy[i];
                int nextDist = curP.dist + 1;

                // 유효하지 못한 좌표 케이스
                if(!isValid(board, nextX, nextY) || visited[nextX][nextY][i] || BLOCK.equals(graph[nextX][nextY])) {
                    continue;
                }

                // 유효한 좌표 && 방문 안함 && 지나갈 수 있는 길
                while(isValid(board, nextX, nextY) && !BLOCK.equals(graph[nextX][nextY])) {
                    visited[nextX][nextY][i] = true;
                    nextX += dx[i];
                    nextY += dy[i];
                }

                // 유효하지 않은 좌표 원상 복구
                nextX -= dx[i];
                nextY -= dy[i];

                // 다음 좌표가 목표 지점인 경우
                if(graph[nextX][nextY].equals(GOAL)) {
                    return nextDist;
                }

                queue.add(new Point(nextX, nextY, nextDist));
            }
        }

        return -1;
    }

    private boolean isValid(String[] board, int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }

    private Point getStartPoint(String[] board) throws Exception {
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++) {
                if(board[row].charAt(col) == 'R') {
                    return new Point(row, col, 0);
                }
            }
        }

        throw new Exception();  // Unreachable Code
    }

    class Point {
        int x;
        int y;
        int dist;

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

 

다른 코드들은 특이한 사항은 없는데 3 차원 배열을 사용해서 문제 기록을 남기게 되었네요.

---

[ 📌 결과 ]

[ 결과 - Java ]

---

[ 📌 마치며... ]

문제를 잘 읽자 !!!

이 문제를 풀며 얻은 교훈이며, 사실 잘 읽었어도 조건 한 번은 수정했을 것 같네요.

 

보기 좋으려고 주어진 String[] 을 String[][] 로 변경 했는데, 알고리즘 문제를 코딩 테스트에서 풀 때 이런 점은 감점 요소가 되는지도 궁금해지는 문제 풀이였습니다.