[알고리즘] Programmers - 리코쳇 로봇

프로그래머스

문제 설명

• 게임 보드판이 1차원 문자형 배열로 주어진다.
• "."은 빈 공간, "R"은 로봇의 처음 위치, "D"는 장애물의 위치, "G"는 목표 지점을 나타낸다.
• 방향은 상, 하, 좌, 우로만 움직일 수 있다.
• 방향을 정하면 장애물이나 맨 끝에 부딪힐 때까지 이동한다.
• 방향을 정해서 움직이고 목표 지점에 도착할 수 있는 최소 움직임(방향을 선택한 수)의 수를 반환해야 한다. 

문제 해결

• 출발지에서 출발을 해서 BFS를 이용해 문제를 해결했다.
• 목표 지점에 도착하면 정수형 변수 answer에 최솟값 갱신했다.
• 델타 탐색을 통해 간단하게 4방향 탐색했다.
• 최단 거리 문제는 BFS를 쓰자.

시간 복잡도

• O(N^2)

풀이 코드

import java.util.*;

class Solution {
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {-1, 1, 0, 0};
    static int N, M, sy, sx, ey, ex, answer;
    static char[][] map;
    static class P {
        int y;
        int x;
        int d;
        public P(int y, int x, int d) {
            this.y = y;
            this.x = x;
            this.d = d;
        }
    }
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        
        map = new char[N][M];        
        for (int y = 0; y < N; y++) {
            map[y] = board[y].toCharArray();
            
            for (int x = 0; x < M; x++) {
                if (map[y][x] == 'R') {
                    sy = y;
                    sx = x;
                    map[y][x] = '.';
                } else if(map[y][x] == 'G') {
                    ey = y;
                    ex = x;
                    map[y][x] = '.';
                }
            }
        }
        
        answer = Integer.MAX_VALUE;
        bfs(sy, sx);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    static void bfs(int y, int x) {
        Queue<P> q = new ArrayDeque<>();
        boolean[][] v = new boolean[N][M];
        
        q.add(new P(y, x, 0));
        v[y][x] = true;
        
        while(!q.isEmpty()) {
            P now = q.poll();
            
            if (now.d >= answer) {
                continue;
            }
            
            if (now.y == ey && now.x == ex) {
                answer = Math.min(answer, now.d);
                continue;
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = now.y;
                int nx = now.x;

                while(true) {
                    int ty = ny + dy[i];
                    int tx = nx + dx[i];

                    if (!isValid(ty, tx)) {
                        break;
                    }

                    ny = ty;
                    nx = tx;
                }
                
                if (v[ny][nx]) continue;
                
                q.add(new P(ny, nx, now.d + 1));
                v[ny][nx] = true;
            }
        }
    }
    
    static boolean isValid(int y, int x) {
        if (y < 0 || y >= N || x < 0 || x >= M) {
            return false;
        } else if (map[y][x] == 'D') {
            return false;
        }
        return true;
    }
}

결과

테스트 케이스 통과 (27 / 27) - DFS와 비교했을 때 눈에 띄게 빠른 것을 볼 수 있다.

---

1차 시도

1. 풀이코드

class Solution {
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {-1, 1, 0, 0};
    static int N, M, sy, sx, ey, ex, answer;
    static char[][] map;
    static boolean[][] v;
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        
        map = new char[N][M];
        v = new boolean[N][M];
        
        for (int y = 0; y < N; y++) {
            map[y] = board[y].toCharArray();
            
            for (int x = 0; x < M; x++) {
                if (map[y][x] == 'R') {
                    sy = y;
                    sx = x;
                    map[y][x] = '.';
                } else if(map[y][x] == 'G') {
                    ey = y;
                    ex = x;
                    map[y][x] = '.';
                }
            }
        }
        
        answer = Integer.MAX_VALUE;
        v[sy][sx] = true;
        dfs(sy, sx, 0);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    static void dfs(int y, int x, int d) {   
        if (d >= answer) {
            return;
        }
        if (y == ey && x == ex) {
            answer = Math.min(answer, d);
            return;
        }            
        for (int i = 0; i < 4; i++) {
            int ny = y;
            int nx = x;
            
            while(true) {
                int ty = ny + dy[i];
                int tx = nx + dx[i];
                
                if (!isValid(ty, tx)) {
                    break;
                }
                
                ny = ty;
                nx = tx;
                 
            }
            
            if (v[ny][nx]) continue;
            
            v[ny][nx] = true;
            dfs(ny, nx, d + 1);
            v[ny][nx] = false;
        }
    }
    
    static boolean isValid(int y, int x) {
        if (y < 0 || y >= N || x < 0 || x >= M) {
            return false;
        } else if (map[y][x] == 'D') {
            return false;
        }
        return true;
    }
}

2. 문제점

• 최악의 경우에 모든 경우의 수를 돌기 때문에 O(V + E) 번의 연산이 이루어져 시간 초과가 발생했다. (V = 10,000 / E = 400,000,000^2)
• answer(최솟값) 보다 크면 더이상 탐색하지 않게끔 가지치기를 했지만 시간 초과 테스트 케이스가 발생했다.

3. 결과

테스트 케이스 통과 (11 / 27)

---

2차 시도

1. 풀이 코드

import java.util.*;

class Solution {
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {-1, 1, 0, 0};
    static int N, M, sy, sx, ey, ex, answer;
    static char[][] map;
    static int[][] v;
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        
        map = new char[N][M];
        v = new int[N][M];
        for (int y = 0; y < N; y++) {
            Arrays.fill(v[y], Integer.MAX_VALUE);
        }
        
        for (int y = 0; y < N; y++) {
            map[y] = board[y].toCharArray();
            
            for (int x = 0; x < M; x++) {
                if (map[y][x] == 'R') {
                    sy = y;
                    sx = x;
                    map[y][x] = '.';
                } else if(map[y][x] == 'G') {
                    ey = y;
                    ex = x;
                    map[y][x] = '.';
                }
            }
        }
        
        answer = Integer.MAX_VALUE;
        v[sy][sx] = 0;
        dfs(sy, sx, 0);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    static void dfs(int y, int x, int d) {   
        if (d >= answer) {
            return;
        }
        if (y == ey && x == ex) {
            answer = Math.min(answer, d);
            return;
        }            
        for (int i = 0; i < 4; i++) {
            int ny = y;
            int nx = x;
            
            while(true) {
                int ty = ny + dy[i];
                int tx = nx + dx[i];
                
                if (!isValid(ty, tx)) {
                    break;
                }
                
                ny = ty;
                nx = tx;
            }
            
            if (v[ny][nx] <= d + 1) continue;
            
            v[ny][nx] = d + 1;
            dfs(ny, nx, d + 1);
        }
    }
    
    static boolean isValid(int y, int x) {
        if (y < 0 || y >= N || x < 0 || x >= M) {
            return false;
        } else if (map[y][x] == 'D') {
            return false;
        }
        return true;
    }
}

2. 1차 시도 코드 개선점

• 방문을 체크하는 논리형 배열 v를 정수형 배열로 바꿔서 현재 위치에서의 움직임 수를 저장하고, 다음에 같은 지점에 방문하는 경우 저장된 움직임 수와 현재 움직임 수를 비교하여 저장된 움직임 수보다 크면 더이상 탐색하지 않도록 했다.

3. 결과

테스트 케이스 통과 (27 / 27)

---

3차 시도 (BFS)

1. 풀이 코드

import java.util.*;

class Solution {
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {-1, 1, 0, 0};
    static int N, M, sy, sx, ey, ex, answer;
    static char[][] map;
    static class P {
        int y;
        int x;
        int d;
        public P(int y, int x, int d) {
            this.y = y;
            this.x = x;
            this.d = d;
        }
    }
    
    public int solution(String[] board) {
        N = board.length;
        M = board[0].length();
        
        map = new char[N][M];        
        for (int y = 0; y < N; y++) {
            map[y] = board[y].toCharArray();
            
            for (int x = 0; x < M; x++) {
                if (map[y][x] == 'R') {
                    sy = y;
                    sx = x;
                    map[y][x] = '.';
                } else if(map[y][x] == 'G') {
                    ey = y;
                    ex = x;
                    map[y][x] = '.';
                }
            }
        }
        
        answer = Integer.MAX_VALUE;
        bfs(sy, sx);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    static void bfs(int y, int x) {
        Queue<P> q = new ArrayDeque<>();
        boolean[][] v = new boolean[N][M];
        
        q.add(new P(y, x, 0));
        v[y][x] = true;
        
        while(!q.isEmpty()) {
            P now = q.poll();
            
            if (now.d >= answer) {
                continue;
            }
            
            if (now.y == ey && now.x == ex) {
                answer = Math.min(answer, now.d);
                continue;
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = now.y;
                int nx = now.x;

                while(true) {
                    int ty = ny + dy[i];
                    int tx = nx + dx[i];

                    if (!isValid(ty, tx)) {
                        break;
                    }

                    ny = ty;
                    nx = tx;
                }
                
                if (v[ny][nx]) continue;
                
                q.add(new P(ny, nx, now.d + 1));
                v[ny][nx] = true;
            }
        }
    }
    
    static boolean isValid(int y, int x) {
        if (y < 0 || y >= N || x < 0 || x >= M) {
            return false;
        } else if (map[y][x] == 'D') {
            return false;
        }
        return true;
    }
}

2. 2차 시도 코드 개선점

• DFS를 통한 방법을 BFS로 바꿔서 진행했다.
• DFS는 방향에 따라 한번이라도 멀게 돌았으면 다른 방향으로 갈 때, 만약 더 짧게 가는 경우가 있어도 모든 케이스를 다 돌아야 한다. (엄청난 중복이 발생한다.) 하지만 BFS는 진짜 최소한의 값으로만 돌기 때문에 중복 탐색이 발생하는 곳이 없다. 

3. 결과

테스트 케이스 통과 (27 / 27) - DFS와 비교했을 때 눈에 띄게 빠른 것을 볼 수 있다.