BOJ: #14502 - 연구소

중간부터 시간 재다가 말았지만, 거의 다섯시간 가까이 붙잡았다. ㅠㅠ

풀기 시작한 지 두 시간이 지났을 때 쯔음에 슬랙에 물어봤고 두 가지 조언을 들었다.

1. board 전체를 돌면서 2가 나올 때마다 BFS를 돌리는 것 보다 2가 있는 위치를 미리 저장해놓고 BFS를 돌리는 게 더 낫다.
2. !visited.contains([nx, ny])의 시간 복잡도가 O(N)이므로 더 빠르게 찾을 수 있는 방법으로 바꿔라.

조언 해주신 대로 1, 2를 수정했다.

1. 2가 있는 위치를 virusLocation에 저장했다.
2. visited를 Set으로 변경했다. Set.contains()의 시간 복잡도는 O(1)

로컬에서는 눈에 띄게 성능 향상이 있었지만 여전히 백준에서는 시간 초과였다. 그래서 스위프트로 통과하신 분의 풀이를 참고했다.

그리고 내 코드에서 다음과 같은 점을 변경했다.

1. 함수를 분리했다.
2. 2차원 배열로 저장했던 virusLocation을 [(Int, Int)] 형태로 저장했다.
3. 바이러스가 퍼져나가는 bfs()에서 visited를 없애는 대신 copyBoard[nx][ny]가 0인지 확인하는 조건으로 변경했다.

아직도 부족한 게 많다는 걸 느꼈다.

문제

https://www.acmicpc.net/problem/14502

내가 작성한 코드

Swift

let size = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = size[0]
let m = size[1]
var board = [[Int]]()
for _ in 0..<n {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    board.append(line)
}
 
var copyBoard = board
var results = [[[Int]]]()
var picked = [[Int]]()
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
 
func makeWall(toPick: Int) {
    if toPick == 0 {
        results.append(picked) // 조합 저장
        return
    }
    for i in 0..<n {
        for j in 0..<m {
            if board[i][j] != 0 {
                continue
            }
            if visited[i][j] {
                continue
            }
 
            visited[i][j] = true
            picked.append([i, j])
            makeWall(toPick: toPick - 1)
            picked.removeLast()
            visited[i][j] = false
        }
    }
}
 
var virusLocation = [(Int, Int)]()
for i in 0..<n {
    for j in 0..<m {
        if board[i][j] == 2 {
            virusLocation.append((i, j))
        }
    }
}
 
func safeArea() -> Int {
    var count = 0
    for i in 0..<n {
        for j in 0..<m {
            if copyBoard[i][j] == 0 {
                count += 1
            }
        }
    }
    return count
}
 
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]
func bfs(_ i: Int, _ j: Int) {
    // 바이러스가 퍼져나가는 작업
    var queue = [(i, j)]
 
    while !queue.isEmpty {
        let v = queue.removeFirst()
        for k in 0..<4 {
            let nx = v.0 + dx[k]
            let ny = v.1 + dy[k]
 
            if !(0..<n ~= nx) || !(0..<m ~= ny) || copyBoard[nx][ny] == 1 {
                continue
            }
            if copyBoard[nx][ny] == 0 {
                queue.append((nx, ny))
                copyBoard[nx][ny] = 2
            }
        }
    }
}
 
makeWall(toPick: 3)
var maxArea = 0
for result in results {
    copyBoard = board
    copyBoard[result[0][0]][result[0][1]] = 1
    copyBoard[result[1][0]][result[1][1]] = 1
    copyBoard[result[2][0]][result[2][1]] = 1
 
    for virus in virusLocation {
        bfs(virus.0, virus.1)
    }
 
    maxArea = max(maxArea, safeArea())
}
 
print(maxArea)