[Algorithm] 백준 - 3055번 탈출 (Swift)

문제 소개

문제 풀이

bfs 를 두번 활용하여 구했다. 물이 퍼지는 것을 moveWater() 로 구현했고, 고슴도치가 움직이는 것도 bfs 를 활용하여 구현했다.

import Foundation

let rc = readLine()!.split(separator: " ").map { Int($0)! }
let (r, c) = (rc[0], rc[1])
let ds = [(1, 0), (0, 1), (-1, 0), (0, -1)]

var map = [[String]]()
var queue: [(Int, Int, Int)] = []
var idx = 0
var widx = 0

var water: [(Int, Int, Int)] = []
var cave = (-1, -1)

for i in 0..<r {
    let input = Array(readLine()!).map { String($0) }
    map.append(input)
    
    for j in 0..<c {
        if input[j] == "S" {
            queue.append((i, j, 0))
        }
        
        if input[j] == "*" {
            water.append((i, j, 0))
        }
        
        if input[j] == "D" {
            cave = (i, j)
        }
    }
}

func moveWater(_ time: Int) {
    while water.count > widx {
        let popped = water[widx]
        if popped.2 > time { break }
        widx += 1
        
        for d in ds {
            let i = popped.0 + d.0
            let j = popped.1 + d.1
                        
            if 0..<r ~= i && 0..<c ~= j {
                if map[i][j] == "." {
                    map[i][j] = "*"
                    water.append((i, j, popped.2 + 1))
                }
            }
        }
    }
}

var visit = Array(repeating: Array(repeating: false, count: c), count: r)

while queue.count > idx {
    let popped = queue[idx]
    idx += 1
    
    moveWater(popped.2)
    
    for d in ds {
        let i = popped.0 + d.0
        let j = popped.1 + d.1
                
        if 0..<r ~= i && 0..<c ~= j {
            if map[i][j] == "." {
                if !visit[i][j] {
                    visit[i][j] = true
                    queue.append((i, j, popped.2 + 1))
                }
            }
            
            if map[i][j] == "D" {
                print(popped.2 + 1)
                exit(0)
            }
        }
    }
}

print("KAKTUS")