[프로그래머스] 미로 탈출 명령어

2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어 문제를 풀어보았다.

 

BFS를 사용하여 접근하였고 사전 순서대로 이동하는 것은 정렬대신,

알파벳 사전 우선순위를 토대로 해당 방향으로 먼저 움직이게 작성하였다.

맨 처음엔 시간 초과가 발생하여 bfs() 메소드 내의 반복문에 적절하게 시간 단축 로직을 추가 작성하였다.

 

BFS

import java.util.LinkedList;
import java.util.Queue;

/**
 * n x m (x, y) -k-> (r, c)
 */
class Solution {
    static int n;
    static int m;
    static int x;
    static int y;
    static int r;
    static int c;
    static int k;
    static String grid[][];
    static int visited[][];

    public String solution(int n1, int m1, int x1, int y1, int r1, int c1, int k1) {
        n = n1;
        m = m1;
        x = x1;
        y = y1;
        r = r1;
        c = c1;
        k = k1;

        int distance = Math.abs(x - r) + Math.abs(y - c);

        // 거리가 안되면 "impossible" 출력
        // (1, 1) -> (6, 1) 인데 k가 4인 경우
        if(distance > k){
            return "impossible";
        }

        // 거리는 되지만 도착지에 도달할 수 없는 경우
        // (1, 1) -> (2, 1)로 갈 때 k가 4인 경우 3의 거리를 가야되는데 나머지 2 했을 때 0이 나오지 않으면 갈 수 없음
        if((distance - k) % 2 != 0){
            return "impossible";
        }

        grid = new String[n+1][m+1];
        visited = new int[n+1][m+1];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i == x && j == y){
                    grid[i][j] = "S";
                }
                else if(i == r && j == c){
                    grid[i][j] = "E";
                }
                else{
                    grid[i][j] = ".";
                }
            }
        }

        String result = bfs(x, y);
        return result;
    }

    private static String bfs(int a, int b) {
        // 알파벳의 우선 순위가 높은 순(사전 순)으로 탐색 진행
        int[] dx = {1, 0, 0, -1};
        int[] dy = {0, -1, 1, 0};
        String[] move = {"d", "l", "r", "u"};

        Queue<Node> q = new LinkedList<>();

        q.add(new Node(a, b, ""));

        // bfs 반복문 시작
        while(!q.isEmpty()){
            Node curr = q.poll();

            int x = curr.x;
            int y = curr.y;
            String cur_str = curr.result;

            // k만큼 이동하고 도착지라면 반환
            if(visited[x][y] == k && x == r && y == c){
                return curr.result;
            }
            else if(visited[x][y] > k){
                break;
            }

            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 시간 초과로 인한 시간 단축 필요
                // 가장 빠른 사전 순위가 정상 진행되면 다른 것은 필요없기 때문에 break
                // 만약, 남은 거리가 k보다 많을 시 해당 과정 무시
                if(1 <= nx && nx <= n && 1 <= ny && ny <= m){
                    if(Math.abs(nx - r) + Math.abs(ny - c) + visited[x][y] + 1 > k)
                        continue;
                    visited[nx][ny] = visited[x][y] + 1;
                    q.add(new Node(nx, ny, cur_str.concat(move[i])));
                    break;
                }
            }
        }
        return "";
    }

    static class Node{
        int x;
        int y;
        String result;

        public Node(int x, int y, String result) {
            this.x = x;
            this.y = y;
            this.result = result;
        }
    }
}

 

 

 

추가로, 풀고 난 뒤 다른 분들은 그리디 방식(?)으로도 푸신 것 같아. 도전하였다.

 

Greedy

import java.util.LinkedList;
import java.util.Queue;

/**
 * n x m (x, y) -k-> (r, c)
 */
class Solution {
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        int distance = Math.abs(x - r) + Math.abs(y - c);

        // 거리가 안되면 "impossible" 출력
        // (1, 1) -> (6, 1) 인데 k가 4인 경우
        if(distance > k){
            return "impossible";
        }

        // 거리는 되지만 도착지에 도달할 수 없는 경우
        // (1, 1) -> (2, 1)로 갈 때 k가 4인 경우 3의 거리를 가야되는데 나머지 2 했을 때 0이 나오지 않으면 갈 수 없음
        if((k - distance) % 2 != 0){
            return "impossible";
        }
        
        String result = "";
        
        // 마찬가지로 dlru가 사전 순
        // 사전 순으로 이동할 수 있는 경우의 수
        int down = Math.max(r - x, 0);
        int left = Math.max(y - c, 0);
        int right = Math.max(c - y, 0);
        int up = Math.max(x - r, 0);
        
        // (0, 0) -> (2, 0), k = 4의 경우 rddl보다 ddud가 사전순으로 높으므로
        // 상쇄되는 경우를 계산
        int balance = (k - distance) / 2;
            
        // 0보다 클 경우 사전 순으로 최대한 이동
        for(int i = 0; i < k; i++){
            if((down > 0 || balance > 0) && x < n){
                result += "d";
                if(down > 0){
                    down--;
                }
                else{
                    balance--;
                    up++;
                }
                x++;
            }
            else if((left > 0 || balance > 0) && y > 1){
                result += "l";
                if(left > 0){
                    left--;
                }
                else{
                    balance--;
                    right++;
                }
                y--;
            }
            else if((right > 0 || balance > 0) && y < m){
                result += "r";
                if(right > 0){
                    right--;
                }
                else{
                    balance--;
                    left++;
                }
                y++;
            }
            else{
                result += "u";
                if(up > 0){
                    up--;
                }
                else{
                    balance--;
                    down++;
                }
                x--;
            }
            
        }
        return result;
    }
}

 

 

Greedy 풀이

 

BFS 풀이

 

속도는 크게 다르지 않지만, BFS가 좀 더 빠른거 같다.