2178 미로 탐색

Today 8/8

BFS

queue를 사용하는 FIFO형식의 탐색방법이다.

미로 탐색 (My Code)

//2178 미로 탐색
let MN = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (MN[0], MN[1])

var graph = [[Int]]()

for _ in 0..<M {
    graph.append(Array(readLine()!).map{Int(String($0))!})
}

var queue = [(Int, Int)]()
var count = Array(repeating: Array(repeating: 0, count: N), count: M)

graph[0][0] = 0
queue.append((0,0))
count[0][0] = 1
while !queue.isEmpty {
    let node = queue.removeFirst()
    for i in [(-1, 0),(1, 0),(0, -1),(0, 1)] {
        let (m,n) = (node.0 + i.0, node.1 + i.1)
        if (0..<M).contains(m) && (0..<N).contains(n) && graph[m][n] == 1 {
            graph[m][n] = 0
            queue.append((m,n))
            count[m][n] = count[node.0][node.1] + 1
        }
    }
}

print(count[M-1][N-1])

count라는 이중배열을 하나 더 만들어서 더 빠르게 걸린 시간을 기록하는 방법을 배웠다.

Array()를 통해 String을 하나씩 쪼개서 배열로 만들어주는 것을 배웠다.

[(-1, 0),(1, 0),(0, -1),(0, 1)]를 통해 주변 경로를 빠르게 대입해주는 법을 배웠다.

(0..<M).contains(m)을 통해 outOfRange를 빠르게 판단하는 법을 배웠다.

미로 탐색 (My Code)

//2178 미로 탐색
let MN = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (MN[0], MN[1])

var graph = [[Int]]()

for _ in 0..<M {
    graph.append(Array(readLine()!).map{Int(String($0))!})
}

var queue = [(Int, Int)]()
var queueNum = 0
var count = Array(repeating: Array(repeating: 0, count: N), count: M)

graph[0][0] = 0
queue.append((0,0))
count[0][0] = 1
while count[M-1][N-1] == 0 {
    let node = queue[queueNum]
    queueNum += 1
    for i in [(-1, 0),(1, 0),(0, -1),(0, 1)] {
        let (m,n) = (node.0 + i.0, node.1 + i.1)
        if (0..<M).contains(m) && (0..<N).contains(n) && graph[m][n] == 1 {
            graph[m][n] = 0
            queue.append((m,n))
            count[m][n] = count[node.0][node.1] + 1
        }
    }
}

print(count[M-1][N-1])

remove를 매 번 해주는게 마음에 들지 않아 index를 통해 현재 노드를 판별하도록 수정해보았다.

그래도 속도는 똑같은듯..

[Swift] 백준 2178 - 미로탐색