[프로그래머스][JAVA][Lv. 2] 리코쳇 로봇

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.HashMap;

class Solution {
    int answer = 123456789;
    char[][] result;
    HashMap<Integer, Integer> visitedMap = new HashMap<>();
    
    public int solution(String[] board) {
        result = new char[board.length][board[0].length()];
        int[] startPos = null;
        
        for (int i = 0; i < result.length; i++) {
            result[result.length - 1 - i] = board[i].toCharArray();
            if (startPos == null) {
                for (int j = 0; j < result[i].length; j++)
                    if (result[result.length - 1 - i][j] == 'R') 
                        startPos = new int[] { j, result.length - 1 - i };
            }   
        }
        move(startPos[0], startPos[1], 0);
        return answer != 123456789 ? answer : -1;
    }
    
    public void move(int x, int y, int count) {
        int key = x * 1000 + y;
        int tempX = x, tempY = y;
        
        if (result[y][x] == 'G') {
            if (answer > count) answer = count;
            return;
        }
        
        if (visitedMap.containsKey(key)) {
            if (visitedMap.get(key) > count) visitedMap.put(key, count);
            else return;
        }
        else visitedMap.put(key, count);
        
        while (true) {  // 상
            if (tempY + 1 == result.length) {
                move(tempX, tempY, count + 1);
                break;
            }
            else {
                if (result[tempY + 1][tempX] == 'D') {
                    move(tempX, tempY, count + 1);
                    break;
                }
                tempY++;
            }
        }
        
        tempY = y;
        while (true) {  // 하
            if (tempY - 1 < 0) {
                move(tempX, tempY, count + 1);
                break;
            }
            else {
                if (result[tempY - 1][tempX] == 'D') {
                    move(tempX, tempY, count + 1);
                    break;
                }
                tempY--;
            }
        }
        
        tempY = y;
        while (true) {  // 좌
            if (tempX - 1 < 0) {
                move(tempX, tempY, count + 1);
                break;
            }
            else {
                if (result[tempY][tempX - 1] == 'D') {
                    move(tempX, tempY, count + 1);
                    break;
                }
                tempX--;
            } 
        }
        
        tempX = x;
        while (true) {  // 우
            if (tempX + 1 == result[tempY].length) {
                move(tempX, tempY, count + 1);
                break;
            }
            else {
                if (result[tempY][tempX + 1] == 'D') {
                    move(tempX, tempY, count + 1);
                    break;
                }
                tempX++;
            }
        }
    }
}

---

후기

전에 풀려고 했다가 도저히 못 풀겠어서 놔뒀던 문제인데 오늘 다시 풀어보니 통과됐다. 그런데 문제는 실행시간이 너무 오래 걸린다... 내가 푼 풀이는 DFS인데 대부분의 사람들이 BFS로 풀었다. 내가 보기에도 깊이 들어가는 것보다는 갈 수 있는 곳을 한꺼번에 처리하는 것이 더 나은 선택같아 보인다. 일단 문제를 풀긴 했지만 나중에 BFS로 다시 풀어봐야 겠다.