리코쳇 로봇(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

출발점(R)에서 부터 동서남북 각 방향에 대해 벽(D)에 도달하기 전까지 이동하면서 도착점(G)까지의 최단 거리 구하기

 

---

 

풀이

 

접근 방식

1. 맵 정보를 이차원 배열에 담는다.

  → 출발점(R)과 도착점(G)의 좌표를 변수에 저장

 

2. bfs를 통한 최단 거리 구하기

  → 출발점에서 bfs 시작. 도착점까지 최단 거리 구하기

 

3. 도착하지 못하는 상황

  → 미끄러지는 그림을 상상했을 때, 도착점(R)의 상하좌우 어느 한 곳에는 반드시 벽(D)이 있어야 도달 가능

 

---

 

코드리뷰

 

import java.util.*;

// 위치 정보를 담을 객체 클래스
class Position {
    int row;
    int col;
    int cnt;	// 거리가 아닌 움직인 횟수를 기록한다.
    public Position(int row, int col, int cnt) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
}

class Solution {
    int N, M;
    boolean[][] visited;	// 방문 여부를 체크하는 배열
    boolean[][] map;	// 맵 정보를 담을 배열
    int rRow, rCol, gRow, gCol;	// 출발점(R)과 도착점(G) 좌표를 담을 변수
    List<Position> list = new ArrayList<>();

	// 최단 거리를 찾는 bfs
    public int bfs(int row, int col) {
        visited[row][col] = true;	// 출발 좌표 방문 체크
        list.add(new Position(row, col, 0));
        while(!list.isEmpty()) {
            Position p = list.remove(0);
            if(p.row == gRow && p.col == gCol) {	// 도착점(G)에 도달했다면
                return p.cnt;	// 이동 횟수(cnt) 리턴
            }
            for(int i = 0; i < 4; i++) {	// 상하좌우 미끄러지기 시작
                if(i == 0) {	// 1. 위로 이동
                    int ROW = p.row;
                    while(true) {
                        ROW--;	// 미끄러지는 과정을 구현하기 위해 while 루프에서 1씩 감소(혹은 증가)시킴
                        if(!map[ROW][p.col]) {	// 벽에 도달했다면
                            if(visited[ROW+1][p.col]) {	// 벽에 도달하기 직전의 좌표의 방문 여부 확인
                                break;	// 방문 했으면 while 루프 탈출(= 미끄러지기 전 위치로 복귀)
                            } else {	// 방문한 적 없다면
                                visited[ROW+1][p.col] = true;	// 방문했음으로 표시
                                list.add(new Position(ROW+1, p.col, p.cnt+1));	// 큐에 추가
                                break;	// 미끄러지기 종료
                            }
                        }
                    }
                } else if(i == 1) {
                    int ROW = p.row;	// 2. 아래로 이동
                    while(true) {
                        ROW++;
                        if(!map[ROW][p.col]) {
                            if(visited[ROW-1][p.col]) {
                                break;
                            } else {
                                visited[ROW-1][p.col] = true;
                                list.add(new Position(ROW-1, p.col, p.cnt+1));
                                break;
                            }
                        }
                    }
                } else if(i == 2) {
                    int COL = p.col;	// 3. 왼쪽으로 이동
                    while(true) {
                        COL--;
                        if(!map[p.row][COL]) {
                            if(visited[p.row][COL+1]) {
                                break;
                            } else {
                                visited[p.row][COL+1] = true;
                                list.add(new Position(p.row, COL+1, p.cnt+1));
                                break;
                            }
                        }
                    }
                } else {
                    int COL = p.col;	// 4. 오른쪽으로 이동
                    while(true) {
                        COL++;
                        if(!map[p.row][COL]) {
                            if(visited[p.row][COL-1]) {
                                break;
                            } else {
                                visited[p.row][COL-1] = true;
                                list.add(new Position(p.row, COL-1, p.cnt+1));
                                break;
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
    public int solution(String[] board) {
        this.N = board.length;
        this.M = board[0].length();
        map = new boolean[N+2][M+2];	// 상하좌우 탐색 시 맵을 벗어나는 것을 방지하기 위해 크기는 +2만큼 설정
        visited = new boolean[N+2][M+2];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                char c = board[i].charAt(j);    // '.' : 경로, 'D' : 벽, 'R' : 출발점, 'G' : 도착점
                if(c == '.') {
                    map[i+1][j+1] = true;
                } else if(c == 'R') {	// 출발점(R) 좌표 저장
                    map[i+1][j+1] = true;
                    rRow = i+1;
                    rCol = j+1;
                } else if(c == 'G') {	// 도착점(G) 좌표 저장
                    map[i+1][j+1] = true;
                    gRow = i+1;
                    gCol = j+1;
                }
            }
        }
        int answer;
        // 도착점의 상하좌우에 벽이 없는지 확인
        if(map[gRow-1][gCol] && map[gRow+1][gCol] && map[gRow][gCol-1] && map[gRow][gCol+1])
            answer = -1;	// 없다면 도달할 수 없음
        else
            answer = bfs(rRow, rCol);	// 벽이 있다면 bfs 시작
        return answer;
    }
}

 

---

 

추가자료

 

포켓몬스터 골드 얼음동굴

출처: 김용녀 Youtube

 

벽이 있는 곳 까지 미끄러진다는 개념을 이해하는데는 얼음동굴이 딱이라고 생각합니다...^^