[코딩테스트]🪧미로 찾기 - Kakao 2023

문제링크

문제링크

난이도

레벨 3

유형

DFS 또는 그리디

소요시간

1시간 30분

회고

DFS 풀이법

어려웠다. k가 2500이라 브루트포스를 통한 조합은 쓰기 어려웠고, dfs를 사용하였다. 나머지 거리 왕복 거리가 % 2 == 0이라는 걸 떠올리기 힘들었다.

 

그리디 풀이법

그리디를 이용하여 풀면 O(k)만에 가능하다. 알파벳 순서대로 접근하고, 최적의 경로를 제외한 경로는 탈출하여 최적화한다.

좌 DFS, 우 Greedy

코드

// DFS 풀이법
func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {
    var answer = ""
    let distance = abs(x - r) + abs(y - c)
    
    if distance > k || ((k - distance) % 2 != 0) {
        return "impossible"
    }
    
    func dfs (_ x: Int, _ y: Int, _ ans : String){
        
        // 가지치기
        guard 
            answer.isEmpty,
            1...n ~= x && 1...m ~= y
        else { return }
        
        guard ans.count + abs(x - r) + abs(y - c) <= k
        else { return }
        
        if ans.count == k {
            if x == r && y == c{
                answer = ans
            }
            return
        }
        
        dfs(x + 1, y, ans + "d")
        dfs(x, y - 1, ans + "l")
        dfs(x, y + 1, ans + "r")
        dfs(x - 1, y, ans + "u")
    }

    dfs(x, y, "")

    return answer
}

// 그리디 풀이법
func greedy(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {
    var answer = ""

    // 사전 불가능 여부 탐색
    let distance = abs(x - r) + abs(y - c)

    if distance > k || (k - distance) % 2 != 0 { return "impossible" }

    var remain = k
    var cr = x
    var cc = y

    var steps: [Character] = ["d", "l", "r", "u"]
    let dr = [1, 0, 0, -1]
    let dc = [0, -1, 1, 0]

    while remain > 0 {
        var moved = false
        for s in (0..<4) {
            let nr = cr + dr[s]
            let nc = cc + dc[s]

            guard (1...n) ~= nr && (1...m) ~= nc else { continue }
            let left = remain - 1
            let leftDistance = abs(nr - r) + abs(nc - c)
            
            // 남은 거리 보다 갈 수 있는 걸음 수가 남아야하고, 그 차이가 정확히 왕복이 가능할 때
            if leftDistance <= left && (left - leftDistance) % 2 == 0 {
                cr = nr; cc = nc
                answer.append(steps[s])
                remain = left
                moved = true
                break
            }
        }
        if !moved { return "impossible" }
    }

    return answer
}