[2023 KAKAO BLIND RECRUITMENT] 미로 탈출 명령어

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

프로그래머스

 

카카오 문제치고 간단하네? 라고 생각했지만 시간 초과.. dfs 문제인데, dfs를 돌지 않아도 되는 예외 상황을 잘 생각해줘야 시간 초과가 나지 않는다.

• dfs를 통해, k만큼 돌고, 현재 위치가 (r, c)에 도착했으면 해당 경로를 리스트에 담으면 된다. 
• 그런데 사전 순으로 가장 빠른 경로 1개만 알아내면 된다. 따라서 루트를 돌 때 애초에 사전 순(d, l, r, u)으로 돌고, 가장 먼저 도착점에 도착하는 루트 1개를 찾았으면 그 루트가 답이 된다. 따라서 이후에는 dfs를 돌지 않아도 된다. 이 부분을 코드로 어떻게 구현해야 하나 막혔었는데.. 그냥 다음과 같이 if(list.size() >= 1)이면 return하도록 하면 된다.

private void dfs(int cnt, int y, int x, String route) {

    // 이미 1개의 루트를 찾았으면 더이상 dfs 진행 X
    if (list.size() >= 1) return;
    ...
}

• 현재 위치에서 도착점까지의 거리가 남은 이동 가능 거리보다 크면 도착이 불가하다. 
• 현재 위치에서 도착점까지의 거리가 홀수이면 남은 이동 가능 거리도 홀수여야 도착이 가능하고, 현재 위치에서 도착점까지의 거리가 짝수이면 남은 이동 가능 거리도 짝수여야 도착이 가능하다.

위 내용들을 코드로 구현하면 된다.

import java.util.*;

class Solution {
    
    int n; int m;
    int x; int y;
    int r; int c;
    int k;
    int[] dx = {0, -1, 1, 0}; 
    int[] dy = {1, 0, 0, -1}; 
    String[] dist = {"d", "l", "r", "u"};
    List<String> list = new ArrayList<>();
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        this.n = n; this.m = m;
        this.x = x; this.y = y;
        this.r = r; this.c = c;
        this.k = k;
        
        dfs(0, x, y, "");
        
        if (list.size() == 0) {
            return "impossible";
        } 
        return list.get(0);
    }
    
    private void dfs(int cnt, int y, int x, String route) {
        // 이미 1개의 루트를 찾았으면 더이상 dfs 진행 X
        if (list.size() >= 1) {
            return;
        }
        
        if (cnt == k) {
            if (y == r && x == c) {
                list.add(route);
            }
            return;
        }
        
        // 도착점까지의 거리, 남은 이동 가능 거리 "거리 비교"
        int distance = getDistance(y, x);
        if (k - cnt < distance) {
            return;
        }
        
        // 도착점까지의 거리, 남은 이동 가능 거리 "짝/홀 비교" (둘 다 짝이거나 홀 == 두 값의 차이가 짝수)
        if (((k - cnt) - distance) % 2 != 0) {
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if (ny <= 0 || ny > n || nx <= 0 || nx > m) {
                continue;
            }
            
            dfs(cnt + 1, ny, nx, route + dist[i]);
        }
    }
    
    public int getDistance(int y, int x) {
        return Math.abs((y - r)) + Math.abs(x - c);
    }
}