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

문제

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

프로그래머스

문제 분석

 

미로의 크기 (n, m) , 시작 위치 (x, y) , 도착지 (r, c), 이동 횟수(k) 가 주어졌을 때 미로를 탈출하기 위한 경로를 구해야 한다.

경로는 l, r, u, d 로 나타내는데 문자열이 사전순으로 가장 빠른 경로로 탈출해야 한다.

 

문제 접근

처음에는 문제를 풀기 위한 특별한 규칙이 없는 거 같아 완전탐색을 통해 문제를 접근하였다.

완전탐색을 통해 가능한 경로들을 다 구한 후 사전순으로 가장 빠른 경로를 리턴하였다.

 

위 방식으로 풀게되면 시간 초과가 발생했다.

완전탐색을 할 때 d->l->r->u 순으로 탐색하게 되면 이때 찾은 경로가 사전순으로 가장 빠른 경로가 된다.

 

이를 적용하더라도 테스트케이스 1개가 시간초과가 난다.

 

현재 위치와 도착지 위치의 거리보다 남은 k 가 더 적으면 탐색을 중지했었는데 이것 말고도 아래와 같은 조건을 추가해줘야 시간 초과가 발생하지 않는다.

 

남은 k 와 가야할 거리의 차이가 짝수가 아니면 이는 해당 위치까지 도달하지 못한다.

 

그 이유는 도착지에 도착하더라도 남은 k가 짝수라면 왔다 갔다 하면서 k를 소모할 수 있지만 

홀수라면 다시 도착지로 돌아오지 못하기 때문이다.

 

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    // 사전순 (d l r u)
    final static int[][] moves = new int[][]{{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    static String result = "impossible";
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        List<String> cur = new ArrayList<>();
        dfs(n, m, x, y, r, c, k, cur);

        return result;
    }
    
    public static void dfs(int n, int m, int curR, int curC, int r, int c, int k, List<String> cur) {
        if (curR == r && curC == c && k==0) {
            result = cur.stream().collect(Collectors.joining());
            return;
        }

        int distance = calculateDistance(curR, curC, r, c);
        
        if (distance > k || Math.abs(k - distance) % 2 != 0) {
            return;
        }

        for (int[] move : moves) {
            int moveR = move[0], moveC = move[1];
            int nextR = curR + moveR, nextC = curC + moveC;

            if (nextR >= 1 && nextR <= n && nextC >= 1 && nextC <= m) {
                if (moveR == 1 && moveC == 0)       cur.add("d");
                else if (moveR == 0 && moveC == -1) cur.add("l");
                else if (moveR == 0 && moveC == 1)  cur.add("r");
                else if (moveR == -1 && moveC == 0) cur.add("u");

                dfs(n, m, nextR, nextC, r, c, k - 1, cur);

                cur.remove(cur.size() - 1);

                if (!result.equals("impossible")) {
                    return;
                }
            }
        }
    }

    public static int calculateDistance(int curR, int curC, int r, int c) {
        return Math.abs(r - curR) + Math.abs(c - curC);
    }
}