[BOJ] 2178 미로탐색

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

분류: BFS

 

---

 

접근

시작점부터 목적지까지 최단 경로를 찾는 전형적인 BFS 문제였습니다. 

 

풀이

방법은 다양하겠으나 저는 거리를 담아두는 distanceMap 이차원 배열을 하나 만들어서 풀었습니다.

import Foundation

let rc = readLine()!.split(separator: " ").map { Int($0)! }
var map = [[Int]]()

for _ in 0..<rc[0] {
    let row = Array(readLine()!).map { Int(String($0))! }
    map.append(row)
}

var distanceMap = [[Int]](repeating: [Int](repeating: 0, count: rc[1]), count: rc[0])

typealias Point = (r: Int, c: Int)
var delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
var queue: [Point] = [(0, 0)]
distanceMap[0][0] = 1

while !queue.isEmpty {
    let (r, c) = queue.removeFirst()
    
    if r == rc[0]-1, c == rc[1]-1 {
        break
    }
    
    for (dr, dc) in delta {
        let nr = r + dr
        let nc = c + dc
        guard nr >= 0, nc >= 0, nr < rc[0], nc < rc[1],
              distanceMap[nr][nc] == 0, map[nr][nc] == 1
        else { continue }
        
        distanceMap[nr][nc] = distanceMap[r][c] + 1
        queue.append((nr, nc))
    }
}

print(distanceMap[rc[0]-1][rc[1]-1])

 

배운점

 

실력이 퇴보했나... 풀이 자체에 큰 차이는 없으나 예전엔 입력받은 배열을 그대로 사용했고 이번엔 거리를 측정하는 배열을 하나 더 만들어서 풀었다는 차이 정도로 보인다