Today 8/23

BFS

queue를 사용하는 FIFO형식의 탐색방법이다.

BRUTE FORCE

말 그대로 전체탐색, 모든 경우의 수를 순회하여 정답을 찾는 탐색방법이다.

알고리즘 기법[전체 탐색] - 브루트 포스(brute force)

연구소 (My Code)

//14502 연구소
let NM = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (NM[0], NM[1])

var map = [[Int]]()
var queue = [(Int, Int)]()
var blank = [(Int, Int)]()
var output = 0

for row in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    input.enumerated().forEach { (index, node) in
        if node == 2 {
            queue.append((row, index))
        }
        if node == 0 {
            blank.append((row, index))
        }
    }
    map.append(input)
}

func BFS(_ map: inout [[Int]]) -> Int {
    var instantQueue = queue
    var index = 0
    while index < instantQueue.count {
        let node = instantQueue[index]
        for i in [(-1, 0),(1, 0),(0, -1),(0, 1)] {
            let (n,m) = (node.0 + i.0, node.1 + i.1)
            if (0..<N).contains(n) && (0..<M).contains(m) && map[n][m] == 0 {
                map[n][m] = 2
                instantQueue.append((n,m))
            }
        }
        index += 1
    }
    var count = 0
    for row in 0..<N {
        for col in 0..<M {
            if map[row][col] == 0 {
                count += 1
            }
        }
    }
    return count
}

for first in 0..<blank.count {
    for second in first+1..<blank.count {
        for third in second+1..<blank.count {
            var instantMap = map
            instantMap[blank[first].0][blank[first].1] = 1
            instantMap[blank[second].0][blank[second].1] = 1
            instantMap[blank[third].0][blank[third].1] = 1
            let result = BFS(&instantMap)
            output = max(output, result)
        }
    }
}

print(output)

설마 하나하나씩 벽(1)을 쌓는게 정답일까 하는 생각에 0,1,2 모두에서 BFS활용해서 정답을 전개해나가려했는데 아무리 생각해도 방법이 없었다.

Brute Force, 진짜 하나씩 3중 for문 돌려서 벽을 세워서 BFS 돌리는게 방법이었다. 방법을 알고나니 구현은 간단했다.

배열로 0, 2인 부분 나열해서 시간 최대한 절약하고, inout 매개변수로 instantMap받아주어서 메모리도 절약했다.

enumerated().forEach { $0 } 로 한 번에 사용할 수 있다는 것을 알았다.
[코딩테스트 대비] 순열(Permutation)과 조합(Combination) 알고리즘