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

문제

프로그래머스

입력

n: Int = 세로 길이
m: Int = 가로 길이
x: Int = 초기 세로 위치
y: Int = 초기 가로 위치 
r: Int = 도착 세로 위치
c: Int = 도착 가로 위치 
k: Int = 제한

결과

이동거리가 k일 때 사전순으로 가장 빠른 방법을 출력 
l = 왼 
r = 오
d = 아래
u = 위

만약 방법이 없다면 impossible 문자열 출력

해석

1. 움직임에 대한 문자가 매칭되야하므로 열거형으로 하면 편할 것 같다.

2. 사전으로 가장 빠른 움직인 순서는 d l r u 순이니 이 순서로 방문을 하면 알아서 사전순은 맞춰질 듯하다.

3. 일단 기본적으로 dfs를 통해 진행을 하면되는데 여기서 현재위치로부터 도착지점까지 최소거리를 항상 체크해준다.

4. 방법이 없는 경우는 크게 2가지가 될 것 같다

• 처음지점부터 도착지점까지 최소거리가 k를 넘을 때 
• k - 최소거리  % 2  != 0 이면 불가능하다. 왜냐하면 짝수면 남은 횟수를 왕복하면되지만 홀수면 왕복이 불가능하여
  다시 도차직점으로 오는 것이 불가능하기 때문이다.

코드

import Foundation

enum Dir : String {
    case d
    case l
    case r
    case u
    
    var coord: (Int, Int) {
        switch self {
            
        case .l:
            return (0, -1)
        case .r:
            return (0, 1)
        case .u:
            return (-1, 0)
        case .d:
            return (1, 0)
        }
    }
    
}

let dirs: [Dir] = [.d, .l, .r, .u]

func minDist(_ x1: Int, _ y1: Int, _ x2: Int,_ y2: Int) -> Int {
    return abs(x1-x2) + abs(y1-y2)
} 

func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {
    // n = 세로 길이
    // m = 가로 길이
    // x = 초기 세로 위치
    // y = 초기 가로 위치 
    // r = 도착 세로 위치
    // c = 도착 가로 위치 
    // k = 제한

    var ans: String = ""
        
    func dfs(_ x:Int, _ y: Int, _ dist: Int, _ record:[String]) {
        
        if  k < (dist + minDist(x,y,r,c)) { // 남은 횟수안에 도착 X
            return 
        }
        
        if dist == k && ( x ==  r && y == c ) { 
            ans = record.joined()
            return
        }
        
        for i in 0..<4 {
            
            let dir = dirs[i]
            let (dx, dy) = dir.coord
            
            let nextX = x + dx
            let nextY = y + dy
        
            if  !(1...n ~= nextX) || !(1...m ~= nextY) || !ans.isEmpty { 
                continue
            }
            
            
            dfs(nextX,nextY,dist+1,record + [dir.rawValue])
            
        }
        
       
    }
    
    if  (k < minDist(x,y,r,c)) || (k-minDist(x,y,r,c)) % 2 != 0   { 
        // 맨해튼 거리보다 짧거나 , 그 차이가 홀 수이면 도착 불가 
        return "impossible"
    }
    
    dfs(x,y,0,[])
    
    
    return ans
}