백준 17136 색종이 붙이기

 

출처: www.acmicpc.net/problem/17136

분류: 완전탐색

---

접근방식

가능한 색종이를 열심히 붙이면 되는 문제였습니다. 

처음엔 크기가 5x5인 색종이부터 먼저 붙여나가는 방식으로 접근했는데 이렇게 되면 틀리더라구요.. 반례가 있나봅니다. 

따라서 백트래킹으로 모든 경우를 찾아주는 방식으로 접근해야 합니다!! 

그리고 이것도 단순히 크기가 1인 색종이부터 확인해나가면 모두 1인 칸일 경우에는 엄청난 연산이 필요하게됩니다.

크기 5부터 접근해서 찾고, 이미 찾은 최소 케이스보다 많이 사용하게되면 그 이상은 무의미하니 거기서 중단해주면 시간을 단축시킬 수 있습니다.

나머지는 단순 구현이라 코드를 보시면 어렵지않게 이해가 되실 것 같습니다 :)

 

해결방법

func solution() {
    typealias Point = (r: Int, c: Int)
    var map = [[Int]]()
    
    for _ in 0..<10 {
        map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
    }
    
    func isAttach(_ p: Point, _ size: Int) -> Bool {
        guard p.r + size <= 10, p.c + size <= 10 else { return false }
        
        for r in p.r..<p.r+size {
            for c in p.c..<p.c+size {
                guard map[r][c] == 1 else {
                    return false
                }
                
            }
        }
        return true
    }
    
    func setPaper(_ p: Point, _ size: Int, attaching: Bool) {
        for r in p.r..<p.r+size {
            for c in p.c..<p.c+size {
                map[r][c] = attaching ? 0 : 1
            }
        }
    }
    
    func checkSuccess() {
        for r in 0..<10 {
            for c in 0..<10 {
                guard map[r][c] == 0 else {
                    return
                }
            }
        }
        if minUseCount == -1 || useCount < minUseCount {
            minUseCount = useCount
        }
    }
    
    var minUseCount = -1
    var useCount = 0
    var remainPapers = [Int](repeating: 5, count: 5+1)
    
    func next(_ p: Point) {
        guard minUseCount == -1 || useCount < minUseCount else { return }
        
        if p.c < 9 {
            brutePaper((p.r, p.c+1))
        } else {
            brutePaper((p.r+1, 0))
        }
    }
    
    func brutePaper(_ p: Point) {
        guard p.r < 10, p.c < 10 else {
            checkSuccess()
            return
        }
        
        guard map[p.r][p.c] == 1 else {
            next(p)
            return
        }
        
        for size in (1...5).reversed() {
            if remainPapers[size] > 0, isAttach(p, size) {
                setPaper(p, size, attaching: true)
                remainPapers[size] -= 1
                useCount += 1
                next(p)
                remainPapers[size] += 1
                useCount -= 1
                setPaper(p, size, attaching: false)
            }
        }
    }
    
    brutePaper((0, 0))
    print(minUseCount)
}

solution()

 

배운점

처음에 문제를 잘못이해해서 엄한 데서 시간을 많이 날려먹었다.

여지없이 잔실수로 또 시간도 날려먹었따.. 

attaching ? 0 : 1 을 해줘야 하는데 attaching ? 1 : 0 이라니... ~_~ 

그리고 쓸데없는 자잘하고 이상한 부분에서 고민하지 말고 컴퓨터의 힘을 믿고 크게크게 생각하자.