[Algorithm] 프로그래머스 - 미로 탈출 (Swift) (DFS, BFS)

문제 소개

프로그래머스

아래와 같은 미로가 ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"] 와 같은 형태로 주어지고, L을 방문했다가 E를 방문하는 최소의 이동거리를 구하는 문제이다.

출처: 프로그래머스

문제 풀이 (DFS, 실패)

처음 문제풀이는 가로, 세로 길이의 범위가 5 이상 100 이하인 조건이 있었기 때문에 숫자가 충분히 크지 않아서 DFS로 충분히 풀 수 있지 않을까? 하는 생각이 들었다. (보통 이런 최단거리문제는 BFS가 맞다)

 

아무튼 나는 move라는 재귀함수를 만들었다. 재귀함수의 탈출조건에 시간을 넣어서 만들었다.

func solution(_ maps: [String]) -> Int {
    var newMap = [Array(repeating: "X", count: maps[0].count+2)]
    let visit = Array(repeating: Array(repeating: false, count: maps[0].count+2), count: maps.count+2)
    var start = (-1, -1)
    var end = (-1, -1)
    var lever = (-1, -1)
    
    for (i, map) in maps.enumerated() {
        var line = ["X"]
        var j = 1
        
        for element in map {
            line.append(String(element))
            if String(element) == "S" {
                start = (i+1, j)
            } else if String(element) == "L" {
                lever = (i+1, j)
            } else if String(element) == "E" {
                end = (i+1, j)
            }
            
            j += 1
        }
        
        line.append("X")
        newMap.append(line)
    }
    
    newMap.append(Array(repeating: "X", count: maps[0].count+2))
    
    var leverTime = 10000
    var endTime = 10000
    
    func move(from: (Int, Int), to: (Int, Int), visit: [[Bool]], time: Int) {
        var visit = visit
        if visit[from.0][from.1] || newMap[from.0][from.1] == "X" { return }
        visit[from.0][from.1] = true
        
        if to == lever {
            if time >= leverTime { return }
        } else if to == end {
            if time >= endTime { return }
        }
        
        if from == to {
            if to == lever {
                leverTime = min(leverTime, time)
            } else if to == end {
                endTime = min(endTime, time)
            }
            return
        }
        
        move(from: (from.0+1, from.1), to: to, visit: visit, time: time+1)
        move(from: (from.0, from.1+1), to: to, visit: visit, time: time+1)
        move(from: (from.0-1, from.1), to: to, visit: visit, time: time+1)
        move(from: (from.0, from.1-1), to: to, visit: visit, time: time+1)
    }
    
    move(from: start, to: lever, visit: visit, time: 0)
    if leverTime != 10000 {
        move(from: lever, to: end, visit: visit, time: 0)
    }
    
    return leverTime == 10000 || endTime == 10000 ? -1 : leverTime+endTime
}

 

많은 테스트 케이스를 통과했지만, 시간초과가 나게 되었다. 4가지의 길을 모두 갈 수 있다면 시간복잡도는 O(4^N^2)가 되기 때문에 4의 100 제곱이 최악의 경우의 수다...

 

문제 풀이 (BFS, 통과)

BFS로 접근했다. 나는 removeLast() 를 활용했기 때문에 stack이라고 이름 지었다. 하지만 끝에 sort과정을 거치기 때문에 LIFO를 지키진 못했다...

 

func solution(_ maps: [String]) -> Int {
    var newMap = [Array(repeating: "X", count: maps[0].count+2)]
    var start = (-1, -1)
    var end = (-1, -1)
    var lever = (-1, -1)
    
    for (i, map) in maps.enumerated() {
        var line = ["X"]
        var j = 1
        
        for element in map {
            line.append(String(element))
            if String(element) == "S" {
                start = (i+1, j)
            } else if String(element) == "L" {
                lever = (i+1, j)
            } else if String(element) == "E" {
                end = (i+1, j)
            }
            
            j += 1
        }
        
        line.append("X")
        newMap.append(line)
    }
    
    newMap.append(Array(repeating: "X", count: maps[0].count+2))
    
    func getTime(_ start: (Int, Int), _ end: (Int, Int)) -> Int {
        var visit = Array(repeating: Array(repeating: false, count: maps[0].count+2), count: maps.count+2)
        var stack = [(start.0, start.1, 0)]
        var directions = [(1,0), (0,1), (-1,0), (0,-1)]
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            
            if visit[node.0][node.1] { continue }
            visit[node.0][node.1] = true
            
            if (node.0, node.1) == end { return node.2 }
            if newMap[node.0][node.1] == "X" { continue }
            
            for direction in directions {
                let next = (node.0+direction.0, node.1+direction.1, node.2+1)
                stack.append(next)
            }
            
            stack.sort(by: { $0.2 > $1.2 } )
        }
        
        return -1
    }
    
    let leverTime = getTime(start, lever)
    if leverTime == -1 { return -1 }
    let endTime = getTime(lever, end)
    if endTime == -1 { return -1 }
        
    return leverTime + endTime
}

 

모든 테스트에서 좋은 실행결과가 나왔다. 테스트 19의 경우 528.29ms에서 1.66ms로 속도도 엄청 개선되었다.

 

DFS, BFS 언제 써야 할까?

문제를 풀다 보니 이런 의문이 들었다. 무조건 BFS가 좋은 거 아닌가? 최단거리, 최소비용경로, 인접한 노드를 탐색해야 할 때는 보통 BFS를 쓰는 것이 좋다. 하지만 BFS의 경우 방문해야 하는 노드들을 저장해야 하기 때문에 메모리 용량을 사용할 수 있다는 단점이 있다.

 

가장 큰 차이점은 넓이가 중요하냐 깊이가 중요하냐의 차이인 것 같다. 최소거리의 경우 가장 짧은 경로가 중요하기 때문에 긴 경로에서는 깊이 들어갈 필요가 없다. 깊이가 중요한 경우는 보다 심층적인 분석이 필요할 때라고 한다... 지금 이해한 바로는 더 깊은 수준에서 끊임없이 변수가 계속 발생할 때 DFS가 필요하다는 정도만 이해했다.