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

문제

 

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

프로그래머스

 

 

풀이

 

처음에 BFS로 풀었는데 시간초과가 나왔다. 이 문제에서는 사전순으로 가장 빠른 경로를 출력해야한다. 그렇기때문에 BFS로 푼다면 가장 빠른 d를 우선으로 탐색하는 것이 아닌, d r l u 골고루 탐색하게되어 불필요한 연산을 하게된다. 

그래서 이 문제는 DFS로 풀어야한다. 기존에 BFS를 이용할때는 queue를 이용하여 removeFirst()로 앞에것부터 빼주면서 돌렸었다. 하지만 DFS를 이용하기 위해서는 stack을 사용하면된다. swift에선 그냥 배열과 동일하지만 stack과 removeLast()를 이용해 탐색하면 DFS가 된다.

 

위와 같은 방법을 이용하기 위해서는 d, l, r, u순으로 탐색해야한다. 그래서 dx와 dy의 순서도 생각해서 정해주어야한다. 

 

이 문제에서 중요한 것은 k이다. 반드시 k만큼 움직여서 목적지에 도착해야한다. 방문했던 곳도 다시 방문할 수 있으므로 탈출조건을 제대로 정해주지 않으면 시간초과가 날 것이다.

 

우선, 남은 거리(k - 이동한 거리)가 현재 지점에서 목적지까지의 최소 거리보다 작아야한다. 

 

다음으로 시작 지점에서 목적지까지의 거리와 k가 모두 홀수이거나 모두 짝수여야한다. 한칸을 이동하게되면 남은거리는 반드시 1칸이 줄어들고 목적지까지의 최소거리는 1이 커지거나 작아질 것이다. 그렇기때문에 하나가 홀수, 하나가 짝수라면 이 조건은 만족할 수 없게된다. 나는 이 조건을 바로 생각못했어서 계속 마지막 케이스에서 계속 시간초과가 났다. 

 

마지막으로, k만큼 움직여서 목적지에 도착했다면 결과를 return해주었다. 위의 방법처럼 DFS로 탐색하면 사전순으로 탐색하기때문에 첫번째로 나온 결과를 바로 출력해주면된다.

import Foundation

func solution(_ n:Int, _ m:Int, _ x:Int, _ y:Int, _ r:Int, _ c:Int, _ k:Int) -> String {

    let start = [x - 1,y - 1]
    let end = [r - 1,c - 1]
    var stack: [([Int], [String])] = [(start, [])]
    let dx = [-1,0,0,1]
    let dy = [0,1,-1,0]
    let remain = (abs(end[0] - start[0]) + abs(end[1] - start[1])) % 2
    
    if k % 2 != remain {
        return "impossible"
    }
    while !stack.isEmpty {
        let current = stack.removeLast()
        if k - current.1.count < abs(end[0] - current.0[0]) + abs(end[1] - current.0[1]) {
            continue
        }
        if current.0 == end && current.1.count == k {
            return current.1.joined()
        }
        for i in 0..<dx.count {
            let newX = current.0[0] + dx[i]
            let newY = current.0[1] + dy[i]
            if newX < 0 || newY < 0 || newX >= n || newY >= m {
                continue
            }
            var word = ""
            switch i {
            case 0:
                word = "u"
            case 1:
                word = "r"
            case 2:
                word = "l"
            default:
                word = "d"
            }
            stack.append(([newX,newY],current.1 + [word]))
        }
    }
    return "impossible"
}

 

 

_____________________________________________________________________________________________________

 

 

카카오문제 어려움..ㅠ