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

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

프로그래머스

---

bfs로 풀이!

특이한 점은, 리코쳇이 벽이나 장애물을 만나기 전까지 계속 한 방향으로 움직인다는 점이었다.

findStopPoint()를 사용하여 리코쳇이 멈추는 지점을 반환하고 이를 bfs로 탐색하여 풀이하였다.

 

첫번째 코드

아래 코드로는 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 5 이 발생하였다..

import java.util.*;

class Point {
    int x;
    int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Solution {
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean visited[][];
    static char map[][];
    static int sum = 0;
    
    public int solution(String[] maps) {
        
        // 1. maps을 2차원 배열 map으로 변환
        int a = maps.length;
        int b = maps[0].length();
        map = new char[a][b];
        visited = new boolean[a][b];
        
        int rI = 0; int rJ = 0;
        for(int i=0; i<a; i++) {
            String str = maps[i];
            for(int j=0; j<b; j++) {
                map[i][j] = str.charAt(j);
                
                if(map[i][j] == 'R') {
                    rI = i;
                    rJ = j;
                }  
            }
        }
        
        // 2. bfs 수행 
        return bfs(rI, rJ);
    }
    
    // 리코쳇이 멈추는 포인트를 찾는 함수
    private static Point findStopPoint(Point p) {
        int nextX = p.x;
        int nextY = p.y;

        for(int i=0; i<4; i++) {
            nextX += dx[i];
            nextY += dy[i];
            
            while(true) {
                if(nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
                    break;                
                }  

                if(map[nextY][nextY] == 'D') {                    
                    break;                
                }
                
                nextX += dx[i];
                nextY += dy[i];
            }
            
            nextX -= dx[i];
            nextY -= dy[i];
        }
        sum += 1;
        return new Point(nextX, nextY);
    }
    
    // BFS 알고리즘
    private static int bfs(int x, int y) { 
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        visited[x][y] = true; 
        
        while(!q.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point p = q.poll();

            // 2. 연결된 곳 순회
            for(int i=0; i<4; i++) {
                Point nextP = findStopPoint(p);
                
                if(map[nextP.x][nextP.y] == 'G') {
                    return sum;
                } else if(!visited[nextP.x][nextP.y]) {
                    q.add(new Point(nextP.x, nextP.y));
                    visited[nextP.x][nextP.y] = true;
                }
            }
        }
        return -1;
    }
}

 

 

아래 코드로는 답이 틀리게 나왔다.. 이유를 정말 한참 찾았다.

import java.util.*;

class Point {
    int x;
    int y;
    int cnt;
    
    public Point(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

class Solution {
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean visited[][];
    static char map[][];
    
    public int solution(String[] maps) {
        
        // 1. maps을 2차원 배열 map으로 변환
        int a = maps.length;
        int b = maps[0].length();
        map = new char[a][b];
        visited = new boolean[a][b];
        
        int rI = 0; int rJ = 0;
        for(int i=0; i<a; i++) {
            String str = maps[i];
            for(int j=0; j<b; j++) {
                map[i][j] = str.charAt(j);
                
                if(map[i][j] == 'R') {
                    rI = i;
                    rJ = j;
                }  
            }
        }
        
        // 2. bfs 수행 
        return bfs(rI, rJ);
    }
    
    // BFS 알고리즘
    private static int bfs(int x, int y) { 
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, 0));
        visited[x][y] = true; 
        
        while(!q.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point p = q.poll();

            // 2. 연결된 곳 순회
            int nextX = p.x;
			int nextY = p.y;
            int cnt = p.cnt;
			
			for(int i=0; i<4; i++) {
                // 4가지 방향으로 탐색
               while(nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] != 'D') {         
                    // 해당 방향으로 최대한 끝까지 이동
					nextX += dx[i];
					nextY += dy[i];
				}
                nextX -= dx[i];
				nextY -= dy[i];
                
                if(visited[nextX][nextY] || (nextX == p.x && nextY == p.y)) {
                    continue;
                } else if(map[nextX][nextY] == 'G') {
                    return cnt + 1;
                }
                
                visited[nextX][nextY] = true;
                q.add(new Point(nextX, nextY, cnt + 1));
			}
        }
        return -1;
    }
}

 

 

최종적으로 성공한 코드는 아래와 같다.

 

nextX, nextY, cnt의 변수 선언을 while문 밑이 아닌 for문 밑으로 변경

차이점이 무엇일까?

4방향으로 탐색하기 위해서는 같은 point의 x, y에서 시작했어야 했는데 전처럼 while문 밑에 선언해버리면 옮겨진 x와 y좌표에서 이어서 탐색을 하게 된다...

어떻게 보면 너무 당연한 거였는데 bfs를 아직 정확히 파악하지 못해 이런 실수가 생긴 것 같다 ㅠ

import java.util.*;

class Point {
    int x;
    int y;
    int cnt;
    
    public Point(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

class Solution {
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean visited[][];
    static char map[][];
    
    public int solution(String[] maps) {
        
        // 1. maps을 2차원 배열 map으로 변환
        int a = maps.length;
        int b = maps[0].length();
        map = new char[a][b];
        visited = new boolean[a][b];
        
        int rI = 0; int rJ = 0;
        for(int i=0; i<a; i++) {
            String str = maps[i];
            for(int j=0; j<b; j++) {
                map[i][j] = str.charAt(j);
                
                if(map[i][j] == 'R') {
                    rI = i;
                    rJ = j;
                }  
            }
        }
        
        // 2. bfs 수행 
        return bfs(rI, rJ);
    }
    
    // BFS 알고리즘
    private static int bfs(int x, int y) { 
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, 0));
        visited[x][y] = true; 
        
        while(!q.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point p = q.poll();

            if(map[p.x][p.y] == 'G') {
                return p.cnt;
            }
			
			for(int i=0; i<4; i++) {
                // 4가지 방향으로 탐색
                int nextX = p.x;
			    int nextY = p.y;
                int cnt = p.cnt;
				
                while(nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] != 'D') {         
                    // 해당 방향으로 최대한 끝까지 이동
					nextX += dx[i];
					nextY += dy[i];
				}
                nextX -= dx[i];
				nextY -= dy[i];
                
                if(visited[nextX][nextY] || (nextX == p.x && nextY == p.y)) {
                    continue;
                } 
                
                visited[nextX][nextY] = true;
                q.add(new Point(nextX, nextY, cnt + 1));
			}
        }
        return -1;
    }
}