Swift - 2178번 미로 [BaekJoon]

 

최단 경로 그래프 탐색 문제

처음에는 그래프 탐색 문제이길래 DFS로 풀어보려 했다. 

 

 

Code. 1 

import Foundation

let NM = readLine()?.components(separatedBy: " ").map{ Int(String($0))! }
let n = NM![0]
let m = NM![1]

var maps = [[Int]]()
var current = [0, 0]
var result = m*m		// 나올 수 있는 최대값

for i in 0..<n {
    let input = readLine()!.map{ Int(String($0))! }
    maps.append(input)
}

DFS(current, 0, [[]])
print(result)

func DFS(_ current:[Int], _ count : Int, _ visited : [[Int]]) {
    //현재 노드 방문했으면 리턴
    guard !visited.contains(current) else { return }

    // 목적지 도착하면 걸린 횟수 저장하고 리턴
    guard current != [m-1, n-1] else {
        if count < result {
            result = count
        }
        return
    }

    let nextNode = [[current[0]+1, current[1]], [current[0]-1, current[1]], [current[0], current[1]+1], [current[0], current[1]-1] ]

    for next in nextNode {
        guard next[0] < m && next[0] >= 0 && next[1] < n && next[1] >= 0 else { continue }
        guard maps[next[1]][next[0]] == 1 else { continue }

        DFS(next, count+1, visited + [current])
    }
}

 

 

답은 잘 나오는데 시간초과가 뜬다.
이유는 DFS와 BFS의 차이에 있었는데, BFS는 가까운 노드부터 확인하기 때문에 목적지에 도착하면 그게 곧 최단 경로이다.
DFS의 경우는 경로에 도달해도 모든 경롤르 다 탐색해봐야 해당 경로가 최단 거리인지 확인 가능하다.
이 부분에서 시간초과로 이어진다. 

 

때문에 최단경로 문제는 BFS로 푸는것이 유리하다.

 

 

 

code. 2

import Foundation

let NM = readLine()?.components(separatedBy: " ").map{ Int(String($0))! }
let n = NM![0]
let m = NM![1]

var maps = [[Int]]()

for i in 0..<n {
    let input = readLine()!.map{ Int(String($0))! }
    maps.append(input)
}

print(BFS())


func BFS() -> Int {
    var count = 0
    var visited = [[Int]]()
    var needToVisit = [[0, 0]]
    var result = Array(repeating: Array(repeating: 0, count: m), count: n)
    
    while !visited.contains([m-1, n-1]) {
        let current = needToVisit.removeFirst()
        
        guard !visited.contains(current) else { continue }
        
        visited.append(current)
        
        let nextNode = [[current[0]+1, current[1]], [current[0]-1, current[1]], [current[0], current[1]+1], [current[0], current[1]-1] ]
        
        for next in nextNode {
            if next[0] < m && next[0] >= 0 && next[1] < n && next[1] >= 0 && maps[next[1]][next[0]] == 1 {
                needToVisit.append(next)
                result[next[1]][next[0]] = result[current[1]][current[0]] + 1
            }
        }
        count += 1
        
    }
    
   return result.flatMap{ $0 }.last! + 1
}