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

문제

리코쳇 로봇

아이디어

bfs 탐색으로 목표지점(G)까지 최소 이동 횟수를 구한다.
👉🏻 큐에 저장할 정보는 현재 좌표(x, y)와 현재 좌표까지의 이동 횟수(c)

이 때 핵심은 한 칸씩 이동하는 것이 아니라 장애물 D가 나타나기 전까지를 1번의 이동으로 친다.
👉🏻 현재 좌표 x, y에서 상하좌우 방향(dx, dy)의 다음 이동할 좌표 nx, ny를 구하기 위해서 반복문이 필요하다.

이동할 다음 좌표 nx, ny를 찾았을 땐,
현재 이동 횟수+1 < 지금까지 저장된 횟수 일 때만 값을 갱신하고 큐에 추가해준다. (그 외는 탐색할 가치가 없음)
👉🏻 최소 이동 횟수를 저장해 둘 2차원 배열이 필요

1. 먼저 출발 지점(R)과 목표 지점(G)을 찾는다.

    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (board[i].charAt(j) == 'R') {
                rx = i;
                ry = j;
                break;
            } else if (board[i].charAt(j) == 'G') {
                gx = i;
                gy = j;
                break;
            }
        }
    }
   

2. 출발지점부터 bfs 탐색을 시작한다.

    Queue<List<Integer>> dq = new LinkedList<>();
    dq.offer(Arrays.asList(rx, ry, 0));
    cnt[rx][ry] = 0;
   

   만약 현재 좌표(x, y)가 목표 지점(gx, gy)이라면 cnt에 최소 값을 갱신해주고 탐색을 종료한다.

   그렇지 않으면 상하좌우 방향(dx, dy)으로 이동 가능한 다음 좌표(nx, ny)를 찾는다.

   이 때, 다음 좌표의 이동 횟수 cnt[nx][ny] < 현재 이동 횟수 c + 1인 경우에 값을 갱신하고 큐에 추가한다.

    while (!dq.isEmpty()) {
        List<Integer> cur = dq.poll();
        int x = cur.get(0);
        int y = cur.get(1);
        int c = cur.get(2);
        if (x == gx && y == gy) {
            cnt[x][y] = Math.min(cnt[x][y], c);
            break;
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            while (0 <= nx && nx < n && 0 <= ny && ny < m && board[nx].charAt(ny) != 'D') {
                nx += dx[i];
                ny += dy[i];
            }
            nx -= dx[i];
            ny -= dy[i];
            if (cnt[nx][ny] > c+1) {
                cnt[nx][ny] = c+1;
                dq.offer(Arrays.asList(nx, ny, c+1));
            }
        }
    }
   

3. 목표 지점의 cnt값을 반환한다.
   (해당 값이 MAX_VALUE라면 탐색 불가능한 경로이므로 -1을 반환)

    return cnt[gx][gy] != Integer.MAX_VALUE ? cnt[gx][gy] : -1;
   

전체 코드

import java.util.*;

class Solution {
    int[] dx = {0, -1, 0, 1};
    int[] dy = {-1, 0, 1, 0};
    int n, m;
    int[][] cnt;
    int rx, ry, gx, gy;
    
    public int solution(String[] board) {
        n = board.length;
        m = board[0].length();
        cnt = new int[n][m];
        for (int[] c: cnt) {
            Arrays.fill(c, Integer.MAX_VALUE);
        }
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (board[i].charAt(j) == 'R') {
                    rx = i;
                    ry = j;
                    break;
                } else if (board[i].charAt(j) == 'G') {
                    gx = i;
                    gy = j;
                    break;
                }
            }
        }

        Queue<List<Integer>> dq = new LinkedList<>();
        dq.offer(Arrays.asList(rx, ry, 0));
        cnt[rx][ry] = 0;
        while (!dq.isEmpty()) {
            List<Integer> cur = dq.poll();
            int x = cur.get(0);
            int y = cur.get(1);
            int c = cur.get(2);
            if (x == gx && y == gy) {
                cnt[x][y] = Math.min(cnt[x][y], c);
                break;
            }
            for (int i=0; i<4; i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                while (0 <= nx && nx < n && 0 <= ny && ny < m && board[nx].charAt(ny) != 'D') {
                    nx += dx[i];
                    ny += dy[i];
                }
                nx -= dx[i];
                ny -= dy[i];
                if (cnt[nx][ny] > c+1) {
                    cnt[nx][ny] = c+1;
                    dq.offer(Arrays.asList(nx, ny, c+1));
                }
            }
        }
        return cnt[gx][gy] != Integer.MAX_VALUE ? cnt[gx][gy] : -1;
    }
}

노트

• 2차원 배열을 특정 값으로 초기화하기
  (파이썬은 리스트 컴프리핸션을 사용한다)

    int[][] arr = new int[4][4];
    for (int[] a: arr) {
        Arrays.fill(a, value);
    }
  

• 큐의 원소로 리스트 넣기

    Queue<List<Integer>> dq = new LinkedList<>();
    dq.offer(Arrays.asList(x, y, 0));