[Algorithm] 백준 - 16197번 두 동전 (Swift)

문제 소개

 

문제 풀이

우선 queue를 사용하였는데 removeFirst()를 사용하지 않고 index를 조절하여 queue를 관리했다. bfs로 푼 이유는 dfs로 끝까지 하는 것보다 최솟값을 찾기에는 bfs가 효과적이다. 나머지는 구현의 문제였다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var map = [[String]]()
var coins = [[Int]]()

for i in 0..<n {
    let input = Array(readLine()!).map { String($0) }
    map.append(input)
    
    for j in input.indices {
        if input[j] == "o" {
            coins.append([i, j])
        }
    }
}

var queue = [(coins[0], coins[1], 0)]
let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

func inBound(_ o: [Int]) -> Bool {
    return o[0] >= 0 && o[0] < n && o[1] >= 0 && o[1] < m
}

var idx = 0

while queue.count > idx {
    let poped = queue[idx]
    idx += 1
    
    let coin1 = poped.0
    let coin2 = poped.1
    let count = poped.2
    
    if count > 10 {
        print(-1)
        break
    }
    
    if !inBound(coin1) && !inBound(coin2) {
        continue
    }
    
    if !inBound(coin1) || !inBound(coin2) {
        print(poped.2)
        break
    }
    
    for direction in directions {
        let (i1, j1) = (coin1[0] + direction.0, coin1[1] + direction.1)
        let (i2, j2) = (coin2[0] + direction.0, coin2[1] + direction.1)
        
        let nextCoin1 = [i1, j1]
        let nextCoin2 = [i2, j2]
        
        if !inBound(nextCoin1) || !inBound(nextCoin2) {
            queue.append((nextCoin1, nextCoin2, poped.2 + 1))
        } else if map[i1][j1] == "#" && map[i2][j2] != "#" {
            queue.append((coin1, nextCoin2, poped.2 + 1))
        } else if map[i1][j1] != "#" && map[i2][j2] == "#" {
            queue.append((nextCoin1, coin2, poped.2 + 1))
        } else if map[i1][j1] != "#" && map[i2][j2] != "#" {
            queue.append((nextCoin1, nextCoin2, poped.2 + 1))
        } else {
            queue.append((coin1, coin2, poped.2 + 1))
        }
    }
}