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

문제

 

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

프로그래머스

 

 

풀이

 

BFS를 이용해 빈 공간과 블럭을 구하고 조건을 만족하도록 구현해주면 되는 문제였다.

 

우선,  game_board와 table에서 각각 bfs를 이용해 빈 공간과 블럭을 구해주었다. 이때, 기준을 맞춰놓기 위해서 블록의 경우는 정렬을 한 뒤에 blocks변수에 넣어주었다.(빈 공간을 기준으로 맞춰도됨)

 

blocks의 각 원소는 하나의 블럭을 이루는 좌표로 이루어져있는데, 편하게 하기 위해서 각 블록의 맨 앞 좌표를 0,0으로 맞춰주었다.

 

이후 구해놓은 빈 공간을 하나씩 확인해가며 count가 같은 경우와 사용되지 않은 것에 대해서만 공간을 회전하며 블럭과 비교해주었다. 시계 방향으로 90도씩 회전한다고 생각하면 x,y가 y,-x가 된다.

이때, 중요한 것은 빈 공간을 회전한 뒤에 다시 정렬을 한 뒤 0,0을 맞춰줘야 블럭과 동일해질 수 있다. 

import Foundation

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
    
    let n = game_board.count
    var boardVisited = Array(repeating: Array(repeating: false, count: n), count: n)
    var tableVisited = Array(repeating: Array(repeating: false, count: n), count: n)
    let dx = [1,0,-1,0]
    let dy = [0,1,0,-1]
    
    var spaces: [[[Int]]] = []
    var blocks: [[[Int]]] = []
    var result = 0
    
    for i in 0..<n {
        for j in 0..<n {
            if !boardVisited[i][j] && game_board[i][j] == 0 {
                var queue = [[i,j]]
                boardVisited[i][j] = true
                var idx = 0
                while idx < queue.count {
                    let current = queue[idx]
                    idx += 1
                    for k in 0..<dx.count {
                        let newX = current[0] + dx[k]
                        let newY = current[1] + dy[k]
                        if newX < 0 || newY < 0 || newX >= n || newY >= n {
                            continue
                        }
                        if !boardVisited[newX][newY] && game_board[newX][newY] == 0 {
                            queue.append([newX,newY])
                            boardVisited[newX][newY] = true
                        }
                    }
                }
                spaces.append(queue)
            }
        }
    }
    
    for i in 0..<n {
        for j in 0..<n {
            if !tableVisited[i][j] && table[i][j] == 1 {
                var queue = [[i,j]]
                tableVisited[i][j] = true
                var idx = 0
                while idx < queue.count {
                    let current = queue[idx]
                    idx += 1
                    for k in 0..<dx.count {
                        let newX = current[0] + dx[k]
                        let newY = current[1] + dy[k]
                        if newX < 0 || newY < 0 || newX >= n || newY >= n {
                            continue
                        }
                        if !tableVisited[newX][newY] && table[newX][newY] == 1 {
                            queue.append([newX,newY])
                            tableVisited[newX][newY] = true
                        }
                    }
                }
                queue = queue.sorted {
                    if $0[0] == $1[0] {
                        return $0[1] < $1[1]
                    }
                    return $0[0] < $1[0]
                }
                blocks.append(queue)
            }
        }
    }
    var check = Array(repeating: false, count: spaces.count) //사용했는지 확인하는 변수
outer: for block in blocks {
        //블럭의 맨 앞을 0,0으로 맞춤
        var current = block
        let x = current[0][0]
        let y = current[0][1]
        for i in 0..<current.count {
            current[i][0] -= x
            current[i][1] -= y
        }
        //space돌아가면서 맞는 공간 있는지 확인
        for i in 0..<spaces.count {
            if spaces[i].count != block.count {
                continue
            }
            //사용된 공간
            if check[i] {
                continue
            }
            var curSpace = spaces[i]
            for _ in 0...3 {
                //정렬하고
                curSpace = curSpace.sorted {
                    if $0[0] == $1[0] {
                        return $0[1] < $1[1]
                    }
                    return $0[0] < $1[0]
                }
                //00맞추고
                let spaceX = curSpace[0][0]
                let spaceY = curSpace[0][1]
                for j in 0..<curSpace.count {
                    curSpace[j][0] -= spaceX
                    curSpace[j][1] -= spaceY
                }
                if curSpace == current {
                    check[i] = true
                    result += curSpace.count
                    continue outer
                }
                //돌려야함
                //90도 회전 x,y => y,-x
                for k in 0..<curSpace.count {
                    let newX = curSpace[k][1]
                    let newY = -curSpace[k][0]
                    curSpace[k] = [newX,newY]
                }
            }
        }
    }
    return result
}

 

 

_____________________________________________________________________________________________________

 

 

이전에 느꼈던 것보다 덜 막막하게 느껴졌다.