[코딩테스트] 🔥 마법 상어의 파이어스톰 - BJ20058_G3

문제링크

문제링크

난이도

골드 3

유형

구현, BFS

소요시간

2시간

회고

구현이 어려운 문제를 하다보니, BFS가 간단해보이는 착각이 일어나는 것 같다. 구현할 때 단순 4분면 교환으로 풀었는데 오답이 나와서, 블로그를 통해 배열 CW 회전을 공부함
https://velog.io/@danbibibi/2차원-배열에서-90도-회전-알고리즘

코드

let NQ = readLine()!.split(separator: " ").map { Int($0)! }
let (N, Q) = (NQ[0], NQ[1])

let LEN =  Int(pow(Double(2), Double(N)))

var A = Array(repeating: Array(repeating: 0, count: LEN), count: LEN)

(0..<LEN).forEach { r in
    let row = readLine()!.split(separator: " ").map { Int($0)! }
    (0..<LEN).forEach { c in
        A[r][c] = row[c]
    }
}

let L = readLine()!.split(separator: " ").map { Int($0)! }

(0..<Q).forEach { head in
    rotate(L[head])
    melt()
}
print(A.flatMap { $0 }.reduce(0, +))
print(bfs())

func bfs() -> Int {
    var visited = Array(repeating: Array(repeating: false, count: LEN), count: LEN)

    let dr = [-1, 0, 1, 0]
    let dc = [0, 1, 0, -1]

    var max = 0

    (0..<LEN).forEach { r in
        (0..<LEN).forEach { c in
            if A[r][c] == 0 || visited[r][c] { return }

            var q: [(Int, Int)] = [(r, c)]
            visited[r][c] = true
            var head = 0

            while head < q.count {
                let (cr, cc) = q[head]
                head += 1

                (0..<4).forEach { k in
                    let nr = cr + dr[k]
                    let nc = cc + dc[k]
                    if nr < 0 || nc < 0 || nr >= LEN || nc >= LEN { return }
                    if visited[nr][nc] || A[nr][nc] == 0 { return }
                    visited[nr][nc] = true
                    q.append((nr, nc))
                }
            }

            if q.count > max { max = q.count }
        }

    }
    return max
}

func rotate(_ l: Int) {
    if l == 0 { return }
    let s = Int(pow(2, Double(l)))
    var next = A
    for sr in stride(from: 0, to: LEN, by: s) {
        for sc in stride(from: 0, to: LEN, by: s) {
            for i in 0..<s {
                for j in 0..<s {
                    next[sr + j][sc + (s - 1 - i)] = A[sr + i][sc + j]
                }
            }
        }
    }

    A = next
}

func melt() {
    let dr = [-1, 0, 1, 0]
    let dc = [0, 1, 0, -1]
    var decs: [(Int, Int)] = []

    for r in 0..<LEN {
        for c in 0..<LEN {
            if A[r][c] == 0 { continue }
            var cnt = 0
            for k in 0..<4 {
                let nr = r + dr[k]
                let nc = c + dc[k]
                if nr < 0 || nc < 0 || nr >= LEN || nc >= LEN { continue }
                if A[nr][nc] > 0 { cnt += 1 }
            }
            if cnt < 3 { decs.append((r, c)) }
        }
    }

    decs.forEach { (r, c) in if A[r][c] > 0 { A[r][c] -= 1 } }
}