문제 링크 (opens new window)

문제

1. 완탐
2. 한 변 길이가 최대 10이므로 좌표 100개 중 3개 선택하는 100C3이 연산횟수
3. 꽃이 죽으면 해당 순회를 즉시 종료하여 최적화 (flowerDead 플래그)

import Foundation

let N = Int(readLine()!)!
var minValue = Int.max
var flower: [[Int]] = .init(repeating: .init(repeating: 0, count: N), count: N)
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: N), count: N)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]

for row in 0..<N {
    flower[row] = readLine()!.split(separator: " ").map { Int($0)! }
}

func combination<T>(_ elements: [T], _ k: Int) -> [[T]] {
    var ret: [[T]] = []

    func combi(_ index: Int, _ now: [T]) {
        if now.count == k {
            ret.append(now)
            return
        }
        for i in index..<elements.count {
            combi(index+1, now + [elements[i]])
        }
    }
    combi(0, [])
    return ret
}

var coords: [(Int, Int)] = []
for i in 1..<N-1 {
    for j in 1..<N-1 {
        coords.append((i, j))
    }
}

let comb = combination(coords, 3)

for choice in comb {
    var price = 0
    visited = .init(repeating: .init(repeating: false, count: N), count: N)
    var flowerDead = false
    for coord in choice {
        if visited[coord.0][coord.1] {
            flowerDead = true
            break
        }
        visited[coord.0][coord.1] = true
        price += flower[coord.0][coord.1]

        for i in 0..<4 {
            let ny = dy[i] + coord.0
            let nx = dx[i] + coord.1

            if visited[ny][nx] {
                flowerDead = true
                break
            }
            price += flower[ny][nx]
            visited[ny][nx] = true
        }
    }

    if flowerDead { continue }

    minValue = min(price, minValue)
}

print(minValue)