[Algorithm] 백준 - 2178번 미로 탐색 (Swift)

문제 소개

https://www.acmicpc.net/problem/2178

미로를 탐색하는 문제이다. 이러한 문제는 가장 최소의 칸수를 구해야 하는 문제이다.
 

문제 풀이

BFS 풀이

미로이기 때문에 한가지 길로 깊게 탐색하는 것보다 넓게 탐색하는 방법을 생각해 보았다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var map = [[Int]]()
var graph = Array(repeating: Array(repeating: 0, count: m), count: n)
var visited = Array(repeating: Array(repeating: false, count: m), count: n)

graph[0][0] = 1
visited[0][0] = true

for _ in 0..<n {
    let line = Array(readLine()!).map { Int(String($0))! }
    map.append(line)
}

func bfs() {
    var queue = [(0, 0)]
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue.count != 0 {
        let poped = queue.removeFirst()
        
        for direction in directions {
            let i = poped.0 + direction.0
            let j = poped.1 + direction.1
            
            if i >= 0 && i < n && j >= 0 && j < m {
                if map[i][j] == 1 && !visited[i][j] {
                    visited[i][j] = true
                    graph[i][j] = graph[poped.0][poped.1] + 1
                    queue.append((i, j))
                }
            }
        }
    }
}

bfs()

print(graph[n-1][m-1])

 

DFS 풀이 (시간초과)

이것은 시간초과가 나왔는데, 많은 테스트케이스를 통과하는 것으로 봐서는... DFS의 문제인 것 같다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var map = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: m), count: n)

for _ in 0..<n {
    let line = Array(readLine()!).map { Int(String($0))! }
    map.append(line)
}

var answer = 1000000

func dfs(_ i: Int, _ j: Int, _ depth: Int) {
    if depth > answer { return }
    
    if i == n-1 && j == m-1 {
        answer = min(depth, answer)
    }
    
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for direction in directions {
        let i = i + direction.0
        let j = j + direction.1
        
        if i >= 0 && i < n && j >= 0 && j < m && !visited[i][j] && map[i][j] == 1 {
            visited[i][j] = true
            dfs(i, j, depth + 1)
            visited[i][j] = false
        }
    }
}

dfs(0, 0, 1)

print(answer)