[프로그래머스] 퍼즐 조각 채우기 (Swift)

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

프로그래머스

 

BFS

이런..복잡해보이는 그림이 나오지만 그래도 들여다보면..생각보단 괜찮은 문제임..

게임보드에서는 빈공간을 BFS로 찾아서 한 블럭의 좌표(x,y) 묶음들을 저장하고

테이블에서는 채워진 공간을 BFS로 찾아서 한 블럭의 좌표 묶음들을 저장해서

그들 중에 서로 일치하는 게 있는지 최대 개수를 세는 문제

 

접근방법

우선 bfs를 사용해서 연결된 한 블럭, 연결된 빈 공간을 찾습니다.

한블럭 : 그 블럭에 속한 칸들의 좌표 집합

그리고 한 블럭씩 회전시키면서 일치하는 빈 공간이 있는지 확인

회전하는 알고리즘은 rotatedR = previousC, rotatedC = maxR-previousR 이다 (시계방향으로 90도 회전)

이때 블럭들을 좌상단으로 밀어붙여줘야하는데, 방법은 R-R최솟값, C-C최솟값 하면 된다.

 

오답노트

6,7,8,9,10,12,13 케이스가 틀렸었는데 문제가 놀랍게도 BFS에서 칸 담을 때 방문여부 체크를 큐에 넣을 때 해줘야 했다는 점..

참고로 visit 배열 따로 안쓰고 방문했으면 1->0, 0->1로 해줬음

 

 

소스코드

import Foundation

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

func rotate(_ block:[[Int]]) -> [[Int]] {
    var newBlock:[[Int]] = []
    let R:Int = block.map { $0[0] }.max() ?? 0
    var minR = 0
    var minC = 0
    for dot in block {
        let nr = dot[1]
        let nc = R-dot[0]
        if minR > nr { minR = nr }
        if minC > nc { minC = nc }
        newBlock.append([nr,nc])
    }
    
    return newBlock.map { a -> [Int] in
        return [a[0]-minR, a[1]-minC]             
     }   
}

func findBlocks(_ table:[[Int]]) -> [[[Int]]] {
    var blocks: [[[Int]]] = []

    // 퍼즐 찾기
    var tb = table
    let T = table.count
    for r in 0..<T {
        for c in 0..<T {
            if tb[r][c] == 1 {
                var block: [[Int]] = []
                var minR = r
                var minC = c
                var q: [[Int]] = []
                q.append([r,c])
                tb[r][c] = 0
                while !q.isEmpty {
                    let now = q[0]
                    if minR > now[0] {
                        minR = now[0]
                    }
                    if minC > now[1] {
                        minC = now[1]
                    }
                    block.append([now[0], now[1]])
                    q.removeFirst()
                    for i in 0..<4 {
                        let nr = now[0]+dr[i]
                        let nc = now[1]+dc[i]
                        if nr >= 0 && nr < T && nc >= 0 && nc < T && tb[nr][nc] == 1 {
                            tb[nr][nc] = 0
                            q.append([nr,nc])
                        }
                    }
                }
                
                // block 하나 확인 (0,0) 기준 재배치
                for i in 0..<block.count {
                    block[i][0] -= minR
                    block[i][1] -= minC
                }
                blocks.append(block)
            }
        }
    }
    return blocks
}

func findEmpties(_ game_board:[[Int]]) -> [[[Int]]] {
    var empties: [[[Int]]] = []

    // 빈공간 찾기
    var gb = game_board
    let G = gb.count
    for r in 0..<G {
        for c in 0..<G {
            if gb[r][c] == 0 {
                var block: [[Int]] = []
                var minR = r
                var minC = c
                var q: [[Int]] = []
                q.append([r,c])
                gb[r][c] = 1
                while !q.isEmpty {
                    let now = q[0]
                    if minR > now[0] {
                        minR = now[0]
                    }
                    if minC > now[1] {
                        minC = now[1]
                    }
                    block.append([now[0], now[1]])
                    q.removeFirst()
                    for i in 0..<4 {
                        let nr = now[0]+dr[i]
                        let nc = now[1]+dc[i]
                        if nr >= 0 && nr < G && nc >= 0 && nc < G && gb[nr][nc] == 0 {
                            gb[nr][nc] = 1
                            q.append([nr,nc])
                        }
                    }
                }
                
                // block 하나 확인 (0,0) 기준 재배치
                for i in 0..<block.count {
                    block[i][0] -= minR
                    block[i][1] -= minC
                }
                empties.append(block)
            }
        }
    }
    
    return empties
}

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
    var answer = 0
    
    var blocks:[[[Int]]] = findBlocks(table)
    var empties:[[[Int]]] = findEmpties(game_board)
    
    // 블록 하나 -> 빈공간에서 같은 거 있나 찾기
    for block in blocks {
        var found = false
        var cur_block: [[Int]] = block
        // 회전
        for i in 0..<4 {
            for (i,em) in empties.enumerated() {
                let a = em.sorted(by: {
                    if $0[0] == $1[0] {
                        return $0[1] < $1[1]
                    } else {
                        return $0[0] < $1[0]
                    }
                })
                let b = cur_block.sorted(by: {
                    if $0[0] == $1[0] {
                        return $0[1] < $1[1]
                    } else {
                        return $0[0] < $1[0]
                    }
                })
                
                if a == b {
                    answer += em.count
                    empties.remove(at:i)
                    found = true
                    break
                }
            }
            if found { break }
            cur_block = rotate(cur_block)
        }
    }
    
    return answer
}