프로그래머스 - 리코쳇 로봇

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

프로그래머스

 

 

 

 

 

문제

• 격자모양 게임판 위에서 말을 움직이는데, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지
• 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다
  • 중간에 G가 나와도 장애물이 아니므로 그냥 지나치게 됨 (문제에는 이 말이 없어서 처음에 이거 이해 못했음)
• "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점

 

• 보드게임판 예시

...D..R
.D.G...
....D.D
D....D.
..D....

"R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있다

 

 

 

 

 

풀이

• 문제 이해하기

처음에 문제를 읽고 예시를 보며 몇 번 움직여야 하는지 알아봤다. 하지만 왜 7번을 움직여야 하는지 이해하지 못했다.

'R 위치에서 아래, 왼쪽' 이렇게 움직이면 2번만에 G를 움직일 수 있는 것이 아닌가? 도저히 이해가 안가서 질문하기 게시판을 봤다. 역시 나처럼 이해를 하지 못한 사람의 게시글이 있었다.. https://school.programmers.co.kr/questions/45898

 

게시판에 달린 댓글을 보고 이해할 수 있었다. 2번째에 왼쪽으로 움직일 때 장애물이 없어서 G를 그냥 지나친다는 것이었다! 포켓몬스터 골드버전의 얼음맵 게임이랑 비슷하다고 한다. https://www.youtube.com/watch?v=QqSREKrNSIg 

 

 

• 격자판에서 상하좌우로 이동을 해 최소 이동 횟수를 구하는 문제로 그래프 탐색 문제이다.
• BFS 사용
  • 말의 위치(행, 열 좌표)와 이동 횟수를 저장하는 Dot 클래스
  • 상하좌우 탐색을 하며 Queue에 Dot 정보를 담고 방문 체크
  • 목표 지점(G)에 도달하면 이동 횟수 반환
  • 큐가 종료되었을 때(목표 지점에 도달할 수 없음), -1 리턴

 

위에까지만 구현하면 전형적인 최소 이동 횟수를 구하는 그래프 탐색 문제와 비슷하다. 하지만 이동 부분에서 달라진다.

 

• 장애물 만나거나 맨 끝에 부딪힐 때까지 미끄러져 이동하기 구현
  • while 문으로 좌표 범위 안에 있고, 장애물을 만나지 않을 때 까지 방향 그대로 이동해주기
  • 그리고 다시 그 방향으로 마이너스를 해주기

 

 

 

 

 

코드

import java.util.*;

class Solution {
    static char[][] graph; //보드 그래프
    static int N, M; //행, 열 크기
    static boolean[][] visited; //방문 여부 채크
    static int[] dx = {-1, 1, 0, 0}; //상하좌우
    static int[] dy = {0, 0, -1, 1};
    
    static class Dot {
        int x, y, dist; //행, 열, 이동 횟수
        
        public Dot(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    
    public int solution(String[] board) {
        N = board.length; 
        M = board[0].length();
        graph = new char[N][M];
        
        int startX = 0, startY = 0;
        
        for(int i = 0; i < N; i++) {
            String str = board[i];
            
            for(int j = 0; j < M; j++) {
                graph[i][j] = str.charAt(j);
                if(graph[i][j] == 'R') {
                    startX = i;
                    startY = j;
                }
            }
        }
        
        visited = new boolean[N][M];
        
        return bfs(startX, startY);
    }
    
    public int bfs(int startX, int startY) {
        Queue<Dot> queue = new LinkedList<>();
        
        queue.add(new Dot(startX, startY, 0));
        visited[startX][startY] = true;
        
        while(!queue.isEmpty()) {
            Dot dot = queue.poll();
            
            for(int d = 0; d < 4; d++) {
                int nx = dot.x + dx[d];
                int ny = dot.y + dy[d];
                
                while((0 <= nx && nx < N && 0 <= ny && ny < M) && (graph[nx][ny] != 'D')) { //장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동
                    nx += dx[d];
                    ny += dy[d];
                }
                
                if(graph[nx - dx[d]][ny - dy[d]] == 'G') { //목표 도달
                    return dot.dist + 1; //최소 이동 횟수 반환
                }
                
                //이동함
                if(!visited[nx - dx[d]][ny - dy[d]]) {
                    queue.add(new Dot(nx - dx[d], ny - dy[d], dot.dist + 1));
                    visited[nx - dx[d]][ny - dy[d]] = true;
                }
            }
            
        }
        
        return -1;
    }
}

 

 

 

 

 

결과

 

 

 

 

배운점

• 프로그래머스는 IDE에서 풀 때보다 디버깅이 어렵고, IndexOutOfBound 나면 어디서 났는지 안알려줘서 에러를 찾기 어려운 노답이라서 실수를 줄여야 겠다고 생각했다.