백준 1261 알고스팟

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

분류: BFS, 다익스트라

---

접근방식

0은 그냥 통과, 1이 있는 칸은 벽을 부수면서 목적지까지 갈 때 최소한 몇 개의 벽을 부숴야하는지 찾는 문제였습니다.

dist 배열을 두고 최소 비용을 갱신해주면서 BFS 탐색을 해주는 방식으로 해결했습니다.

 

해결방법

let mn = readLine()!.split(separator: " ").map { Int(String($0))! }
let (m, n) = (mn[0], mn[1])
let delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
var map = [[Int]]()

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

var dist = [[Int]](repeating: [Int](repeating: 100000, count: m), count: n)

func search(_ row: Int, _ col: Int) {
    var queue = [(Int, Int)]()
    queue.append((0, 0))
    dist[0][0] = 0
    
    while !queue.isEmpty {
        let (r, c) = queue.removeFirst()
        
        for d in delta {
            let nr = r + d.0, nc = c + d.1
            guard nr >= 0, nr < n, nc >= 0, nc < m else { continue }
            
            if dist[nr][nc] > dist[r][c] + map[nr][nc] {
                dist[nr][nc] = dist[r][c] + map[nr][nc]
                queue.append((nr, nc))
            }
        }
    }
}

search(0, 0)
print(dist[n-1][m-1])

 

배운점