[백준] 알고스팟 (1261번) Swift

문제 내용

M x N 의 미로가 주어진다.

0은 벽이 없는 곳이고, 1은 벽이 있는 곳이다.

목적지 (M, N) 까지 가는데 최소한 벽을 몇 개 부수어야 하는지 구해라.

---

전체 코드

// 1. M x N 읽어옴
let size = readLine()!.split { $0 == " " }.map { Int(String($0))! }
// 2. 미로 저장할 배열
var maze: [[Int]] = Array(repeating: [], count: size[1])
// 3. 해당 위치에 도착하는데 벽을 몇 개 부셨는지 저장하기 위한 배열
var weights: [[Int]] = Array(repeating: Array(repeating: size[0] + size[1] - 2, count: size[0]), count: size[1])
// 4. queue
var queue: [(x: Int, y: Int, weight: Int)] = []
var queueIndex = 0

// 5. maze 에 값 넣기
for i in 0..<size[1] {
    let row = readLine()!.map { Int(String($0))! }
    maze[i] = row
}

// 6. 초기 값 넣기 (0, 0) 에서 시작하고 벽을 0개 부숨 -> (0, 0, 0)
queue.append((0, 0, 0))

while queueIndex < queue.count {
    let now = queue[queueIndex]
    queueIndex += 1
    
    // 7. 만약 현재 읽은 weight (벽 몇개 부셨는지) 가 저장되어있는 weight 보다 작으면
    if now.weight < weights[now.x][now.y] {
        // 8. 갱신하고
        weights[now.x][now.y] = now.weight
        // 9. 그 값을 방문함
        visit(now.x, now.y, now.weight)
    }
}

// 10. 방문 함수
func visit(_ x: Int, _ y: Int, _ weight: Int) {
    // 11. 이동할 x, y 설정
    let moves: [(x: Int, y: Int)] = [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]
    
    for move in moves {
        // 12. 만약 이동이 가능하고 (배열의 범위 내에 있고)
        if move.x >= 0 && move.x < size[1] && move.y >= 0 && move.y < size[0] {
            // 13. 미로 값이 1이면 (벽이면)
            if maze[move.x][move.y] == 1 {
                // 14. 만약 그 위치의 값이 weight + 1 보다 크면
                if weights[move.x][move.y] > weight + 1 {
                    // 15. queue 에 넣음
                    queue.append((move.x, move.y, weight + 1))
                }
            // 16. 만약 미로 값이 0이면 (그냥 갈 수 있으면)
            } else {
                // 17. 만약 그 위치의 값이 weight 보다 작으면
                if weights[move.x][move.y] > weight {
                    // 18. queue 에 넣음
                    queue.append((move.x, move.y, weight))
                }
            }
        }
    }
}

print(weights[size[1] - 1][size[0] - 1])

---

결론

BFS 알고 있으면 풀 수 있는 것 같다.

가로의 크기가 M 이고 세로의 크기가 N 인게 반대 같은 느낌이라 이상했다.

 

출처 : 백준 알고스팟
https://www.acmicpc.net/problem/1261

1261번: 알고스팟