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

홍성진·2023년 3월 18일
0

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

주어진 보드에 시작지점, 장애물, 목표지점이 표기돼있으며 이동은 sliding으로만 가능합니다. 이때 목표지점에 도달하는 최소 sliding 횟수를 구하는 문제입니다. 최소 횟수를 구해야하므로 bfs가 제격입니다.

먼저 addQueueR method로 시작지점의 좌표를 queue에 넣어 탐색을 시작합니다.

목표지점에 도달할 수 없는 경우를 판별하기 위해 visited array를 만들어 방문여부를 판별합니다. 이 때, 직전에 어디서부터 현재지점으로 sliding 해왔는 지는 다음 sliding 지점에 영향을 주지 않습니다. 현재지점엔 다시 올 필요가 없으니 무조건 현재지점을 바로 방문처리 하면 되고, 더이상 방문할 수 있는 곳이 없어지면 목표지점에 도달할 수 없는 겁니다.

sliding을 구현하느라 코드가 너무 길어서 줄여본다고 줄였는데 쉽지 않네요.

import java.util.*;

class Solution {
    Queue<int[]> queue = new LinkedList<>();
    
    public int solution(String[] board) {
        boolean[][] visited = new boolean[board.length][board[0].length()];
        
        addQueueR(board);
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            int step = cur[2];
            
            if (visited[r][c] == true) {
                continue;
            }
            visited[r][c] = true;
            
            if (board[r].charAt(c) == 'G') {
                return step;
            }

            bfs(board, visited, cur);
        }
        return -1;
    }
    
    public void bfs(String[] board, boolean[][] visited, int[] cur) {
        int step = cur[2];
		int sr;
        int sc;
        
        // slide Down        
        sr = cur[0];
        sc = cur[1];
        while (sr != board.length && board[sr].charAt(sc) != 'D') {
            sr++;
        }
        if (visited[--sr][sc] == false) {
            queue.add(new int[] {sr, sc, step + 1});
        }

        // slide Up        
        sr = cur[0];
        sc = cur[1];
        while (sr != -1 && board[sr].charAt(sc) != 'D') {
            sr--;
        }
        if (visited[++sr][sc] == false) {
            queue.add(new int[] {sr, sc, step + 1});
        }

        // slide Right        
        sr = cur[0];
        sc = cur[1];
        while (sc != board[0].length() && board[sr].charAt(sc) != 'D') {
            sc++;
        }
        if (visited[sr][--sc] == false) {
            queue.add(new int[] {sr, sc, step + 1});
        }

        // slide Left        
        sr = cur[0];
        sc = cur[1];
        while (sc != -1 && board[sr].charAt(sc) != 'D') {
            sc--;
        }
        if (visited[sr][++sc] == false) {
            queue.add(new int[] {sr, sc, step + 1});
        }
    }
    
    public void addQueueR(String[] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length(); j++) {
                if (board[i].charAt(j) == 'R') {
                    queue.add(new int[] {i, j, 0});
                    return;
                }
            }
        }
    }
}

0개의 댓글