프로그래머스 - 위클리 챌린지 3주차 - 퍼즐 조각 채우기 - swift

 

https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

 

 

구현문제에 완전탐색과도 같다. 

여기서 핵심을 빠르게 짚어야하는데, 조각을 보드판에 채우기위해서는 꼭 맞아떨어져야 한다는 점이다.

즉, 하나의 조각이 보드판의 빈칸들중에서 여러곳으로 들어갈 수 있다고 해도, 한곳에만 들어가면 된다는 점이다.

 

우선, 문제를 풀기위해서는 도형을 회전할 줄 알아야한다. 

 

도형을 찾기위해서는, 우선 테이블위에 연속된 1들을 bfs로 탐색하여 연속된 도형들을 찾아낸다.

그리고, 연속된도형들을 [(Int, Int)]로 만들어주는데, 항상 첫번째 값이 0,0이 되도록 만들어준다. ( 나중에 이 도형을 가지고 보드판에 넣을때 편하기 위함 ) 

 

그러면, 도형을 찾았으면, 회전하는데, 총 3번회전한 값을 각각 [(Int, Int)] 로 만들어준다. 

마찬가지로 회전한 값의 첫번째값이 0,0되도록 해준다.

 

그럼 각 도형마다 4개의 연속된 (Int,Int)들이 존재하게 되고,

보드판을 전부탐색하면서, 들어갈 수 있는 도형을 넣어주면 된다. 

 

처음에 한곳에만 들어가면 된다는 점을 제대로 인지하지 못하고, 순열로 만들어서 탐색하느라 시간초과됐다. 

 

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
    let N = table.count
    let dir = [(0,1),(0,-1),(1,0),(-1,0)]
    
    func blockList() -> [[(Int,Int)]] {
        var check = Array(repeating: Array(repeating: false, count: N ), count: N )
        var blockList: [[(Int,Int)]] = []
        for i in 0..<N {
            for j in 0..<N {
                if !check[i][j], table[i][j] == 1 {
                    check[i][j] = true
                    var list: [(Int,Int)] = []
                    var queue = [(i,j)]
                    while !queue.isEmpty {
                        let f = queue.removeFirst()
                        list.append(f)
                        for k in 0..<4 {
                            let n = (f.0+dir[k].0, f.1+dir[k].1)
                            if n.0>=N||n.1>=N||n.0<0||n.1<0||check[n.0][n.1]||table[n.0][n.1] == 0 { continue }
                            check[n.0][n.1] = true
                            queue.append((n))
                        }
                    }
                    let f = list.first!
                    blockList.append(list.map{ ($0.0 - f.0, $0.1 - f.1)})
                }
            }
        }
        return blockList
    }
    
    func rotateBlockList() -> [[[(Int, Int)]]] {
        return blockList().map{ block -> [[(Int, Int)]] in
            var list: [[(Int,Int)]] = []
            list.append(block)
            var t = block.map{(-$0.1, $0.0)}
            list.append(t.map{ ($0.0 - t.first!.0, $0.1 - t.first!.1)})
            t = block.map{($0.1, -$0.0)}
            list.append(t.map{ ($0.0 - t.first!.0, $0.1 - t.first!.1)})
            t = block.map{(-$0.0, -$0.1)}
            list.append(t.map{ ($0.0 - t.first!.0, $0.1 - t.first!.1)})
            return list
        }
    }
    
    let blocks = rotateBlockList()
    var board = game_board
    var blockCheck = Array(repeating: false, count: blocks.count)
    
    func find() -> Int {
        var sum = 0
        for i in 0..<N {
            for j in 0..<N {
                for l in 0..<blocks.count {
                    if blockCheck[l] { continue }
                    for k in 0..<4 {
                        if board[i][j] == 0 {
                            let block = blocks[l][k]
                            var isFaile = false
                            
                            // 우선 넣어본다.
                            block.forEach {
                                let n = (i+$0.0, j + $0.1)
                                if n.0>=N||n.1>=N||n.0<0||n.1<0{
                                    isFaile = true
                                    return
                                } else if board[n.0][n.1] >= 1 {
                                    isFaile = true
                                    board[n.0][n.1] += 1
                                } else {
                                    board[n.0][n.1] += 1
                                }
                            }
     
                            // 주변에 여백이있는지 확인한다.
                            block.forEach {
                                let n = (i+$0.0, j + $0.1)
                                if n.0>=N||n.1>=N||n.0<0||n.1<0 { return }
                                
                                for m in 0..<4 {
                                    let nn = (n.0+dir[m].0, n.1+dir[m].1)
                                    if nn.0>=N||nn.1>=N||nn.0<0||nn.1<0 {
                                        continue
                                    }
                                    if board[nn.0][nn.1] == 0 {
                                        isFaile = true
                                        break
                                    }
                                }
                            }
                            
                            // 실패했다면, 다시 넣은 도형을 걷어준다.
                            if isFaile {
                                block.forEach {
                                    let n = (i+$0.0, j + $0.1)
                                    if n.0>=N||n.1>=N||n.0<0||n.1<0{ return }
                                    board[n.0][n.1] -= 1
                                }
                                continue
                            } else {
                                blockCheck[l] = true
                                sum+=block.count
                                break
                            }
                        }
                    }
                }
            }
        }
        return sum
    }

    return find()
}