문제 링크

카카오 코딩테스트: 미로 탈출 명령어

문제 분석

미로 탈출 조건

  • 격자 바깥으로 나갈 수 없다.
  • (x, y)부터 (r, c) 까지 이동거리가 k여야 한다.
  • 같은 격자를 두 번 이상 방문해도 된다.
  • 탈출 경로(문자열)가 사전 순으로 가장 빠른 경로로 탈출해야 한다.예를들어 탈출 경로가 (lldud, dllrl) 가 있으면, dllrl 가 정답이다.
  • 만약 탈출할 수 없는 경우 “impossible” 를 출력한다.

내 코드

가장 직관적인 방법

  1. 사전 순으로 가장 빠른 방향부터 선택하도록 dx, dy를 놓고
  2. 이동 횟수가 k가 되면 return (이 때까지의 커멘드를 정답 후보에 넣는다.)
  3. 모든 탐색을 마친 뒤 정답 후보에서 사전순으로 가장 빠른 문자열을 고른다.
import Foundation

func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {
    // d, l, r, u
    let dx = [1, 0, 0, -1]  // 아래, 왼쪽, 오른쪽, 위
    let dy = [0, -1, 1, 0]
    let directions = ["d", "l", "r", "u"]
    var ret: [String] = []
    func go(_ x: Int, _ y: Int, _ dist: Int, _ a: String) {
        if dist == k {
            if x == r && y == c {
                ret.append(a)
            }
            return
        }
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 1 || nx > n || ny < 1 || ny > m { continue }
            go(nx, ny, dist + 1, a + directions[i])
        }
    }
    
    go(x, y, 0, "")
    if ret.isEmpty {
        return "impossible"
    }
    return ret.sorted().first!
}

그러나 이 코드는 모든 방향 (4 방향)을 최대 k번 탐색하는 것을 반복해야 한다. 따라서 시간 복잡도는 O(4^k) 이며, k는 2,500 으로 시간초과가 날 수 있다.

따라서, 이 코드까지 작성 오기 전에 미리 ‘아, 시간초과가 나겠구나’ 생각하고 방법은 빠르게 바꿔야 한다.

이 문제를 푸는 방법은

  • 이동을 시작할 때부터 가장 빠른 문자로 이동하는 것이 무조건 좋다.
  • 위치 (x, y)에서 k번 이동까지 남은 이동 횟수 remain이 정해지면, 해당 상태에서 탈출까지 최적의 경로는 하나다.
  • remain = k - 현재 이동 횟수
import Foundation

func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {
    var result = "impossible"
    
    func go(_ x: Int, _ y: Int, _ path: String) {
        // 이미 최적의 해를 찾았으므로 return
        if result != "impossible" { return }
        
        let dist = abs(x - r) + abs(y - c)
        let canGo = k - path.count
        
        if canGo < dist || (canGo - dist) % 2 == 1 { return }
        if canGo == 0 && dist == 0 {
            result = path
            return
        }
        
        if x < n { go(x + 1, y, path + "d") }
        if 1 < y { go(x, y - 1, path + "l") }
        if y < m { go(x, y + 1, path + "r") }
        if 1 < x { go(x - 1, y, path + "u")}
    }
    go(x, y, "")
    
    return result
}

배운 점

리팩토링 코드

정리