[Algorithm] 프로그래머스 - 미로 탈출 명령어 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 미로 탈출 명령어 자바 풀이에 대해 작성하고자 합니다.

해당 문제는 카카오 채용 Lv3 문제로 많은 생각을 고려하는 문제였습니다.

 

최초 풀이는 BFS를 활용하였지만 메모리 초과가 발생하였습니다.

따라서, 보다 효과적으로 문제를 어떻게 풀이하면 좋을까 고민하다 문제를 자세히 읽어본 후 힌트를 얻을 수 있었습니다.

이전처럼 소스부터 정리한 후, 풀이 과정을 상세하게 정리하겠습니다.

 

문제 출처: 

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

프로그래머스

 

 

1. 풀이 소스:

 

class Solution {
    
    Node node;
    int row; // 행 범위
    int col; // 열 범위
    int targetX; // 목표 x좌표
    int targetY; // 목표 y좌표
    int targetStep; // 만족해야하는 스텝 수
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        
        row = n + 1; 
        col = m + 1;
        targetX = r; 
        targetY = c;
        targetStep = k;
        node = new Node(x, y); // 출발 노드 설정
    
        while(node.step <= targetStep) {
            if (node.step == targetStep) {
                if (node.x == targetX && node.y == targetY) {
                    return node.answer;
                }
            }
            
            if (isPossibleD()) { // 아래로 갈 수 있는 조건을 만족한다면 x++ (행을 내려야 하므로 +)
                node.x++;
                node.answer += "d";
            } else if (isPossibleL()) { // 다음 우선 순위로 L 탐색 가능 확인
                node.y--;
                node.answer += "l";
            } else if (isPossibleR()) { // d, l로 갈 수 없다면 r 가능 여부 확인
                node.y++;
                node.answer += "r";
            } else if (isPossibleU()) { // 마지막 우선순위 u 확인
                node.x--;
                node.answer += "u";
            } else { // 위의 분기문을 먼저 고려한 결과 해당하지 않는다면 탈출
                answer = "impossible"; 
                break;
            }
            
            node.step++; // break되지 않았다면 어느 한 방향으로 움직였다는 의미이므로 step++
        }
        
        
        return answer;
    }
    
    
    class Node {
        int x;
        int y;
        int step;
        String answer = "";
        
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    boolean isPossibleD() { // down은 행을 내려야하므로 +
        return node.x > 0 && node.x < row - 1 && isPossibleMove(node.x + 1, node.y);
    }
    
    boolean isPossibleU() { // up은 행을 올려야 하므로 -
        return node.x > 1 && (node.x < row) && isPossibleMove(node.x - 1, node.y);
    }
    
    boolean isPossibleL() { // left는 열을 왼쪽으로 가야하므로 -
        return node.y > 1 && node.y < col && isPossibleMove(node.x, node.y - 1);
    }
    
    boolean isPossibleR() { // right는 열을 오른쪽으로 가야하므로 +
        return node.y > 0 && (node.y < col - 1) && isPossibleMove(node.x, node.y + 1);
    }
    
    // 하단에 자세하게 설명하였습니다.
    boolean isPossibleMove(int x, int y) {
        return Math.abs(targetX - x) + Math.abs(targetY - y) + node.step + 1 <= targetStep;
    }
    
}

 

 

2. 풀이 방법

 

문제는 k개의 문자열의 길이를 반드시 유지하면서 사전 순으로 탐색하라고 되어있습니다. 이는 곧 갈 수 있는 거리가 여러 개 있더라도 탐색은 사전순으로 하라는 것을 의미합니다.

 

기존 BFS 혹은 DFS 탐색은 상하좌우 형태로 무작위로 실행하되 완전 탐색 혹은 백트래킹 형태로 진행됩니다.

하지만, 사전순으로 탐색을 하게 된다면 무조건 가깝게 갈 수 있다면 가깝게 이동하도록 구현할 수 있습니다.

 

가령 A - B까지 (10, 0) 만큼 차이가 있고 14번의 움직임이 필요하다면 

d * 10 + 이후 d - l - r - u로 움직이면 됩니다.

 

즉, 최대한 사전으로 움직일 수 있는 만큼 while문으로 움직이되 isPossibleMove라는 메서드에
다음에도 움직일 수 있는 범위가 유효한지 판단하기 위해  현재 step + 1과 목표 targetX, targetY (좌표)에서 현재 위치한 좌표를 빼서 타깃보다 같거나 작은 경우를 체크합니다.

 

이 제약 조건은 다음을 의미합니다.

 

만약, 해당 조건을 만족하지 않는 경우에는 예를 들어 최대 앞으로 움직일 수 있는 step이 10인데, 총거리가 10을 초과해 버리면 그 경로는 절대 목표점으로 갈 수가 없습니다.

 

따라서, while문으로 아래, 좌, 우, 위 방향으로 탐색을 진행하도록 하되, 해당 방향으로 이동했을 때 목표 step안에 도착할 수 없는 경로라면 if - else if - else 문으로 가능한 우선순위로 다시 움직이게 되고 전부 갈 수 없다면 else로 while문을 빠져나옵니다.

 

기타 자세한 풀이는 주석으로 설정하였습니다.

 

 

 

BFS 풀이 후 메모리 초과가 발생하여, 혹시 이 방법은 어떨까 불현듯 생각난 방법으로 풀었는데 한 번에 성공하여, 계속 꾸준히 알고리즘 문제를 푸니 정말 많이 성장했다는 점을 느끼게 되었습니다.

 

혹시 이 문제로 메모리 초과 혹은 시간초과가 발생하신다면, 저와 비슷한 방법으로 풀어보시면 좋을 것 같습니다.

이상으로 글을 마치도록 하겠습니다. 감사합니다.!!!