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

 

Problem

 

코딩테스트 연습 - 3주차

---

Solution

 

1. 게임보드와 테이블의 퍼즐 조각들을 찾는다.

 

게임보드와 테이블의 퍼즐 조각들을 찾기 위해선 BFS 알고리즘을 사용해야 됩니다.

 

게임보드를 탐색할 땐 만약 0을 만나게 되었다면 그 주변 왼쪽,오른쪽,위,아래가 0인지를 파악합니다.

 

만약 0이라면 큐에 해당 위치를 넣고 반복해줘서 퍼즐의 조각을 완성합니다.

 

func makePuzzle(x:Int,y:Int,isEmpty:Bool) {
    var queue:[(Int,Int)] = [(x,y)]
    while !queue.isEmpty {
        let first = queue.removeFirst()
        let new = [(first.0-1,first.1),(first.0+1,first.1),(first.0,first.1-1),(first.0,first.1+1)]
        
        for d in new {
            if 0..<boardCopy.count ~= d.0 && 0..<boardCopy.count ~= d.1 {
                if boardCopy[d.1][d.0] == 0 {
                    boardCopy[d.1][d.0] = 1
                    if isEmpty {
                        emptyBlocks[emptyBlocks.count-1].append(d)
                    }else {
                        blocks[blocks.count-1].append(d)
                    }
                    queue.append(d)
                }
            }
        }
    }
}

 

2. 테이블의 퍼즐 조각을 회전해준다.

 

게임보드와 테이블의 퍼즐 조각이 같은지 확인하기 위해선 테이블의 각 0,90,180,270도로 회전된 퍼즐 조각들을 비교해주어야 합니다.

 

90도 시계방향으로 회전하는 공식은 (x,y) -> (y,-x)입니다.

 

func rotateBlocks(block:[(Int,Int)]) -> [[(Int,Int)]] {
    var newBlock = block
    var rotateBlocks:[[(Int,Int)]] = [block]
    
    for _ in 0..<3 {
        var rotateBlock:[(Int,Int)] = []
        for b in newBlock {
            rotateBlock.append((b.1,-b.0))
        }
        newBlock = rotateBlock
        rotateBlocks.append(rotateBlock)
    }
    return rotateBlocks
}

 

3. 게임보드와 테이블의 퍼즐 조각을 모두 비교해줍니다.

 

게임보드와 테이블의 퍼즐 조각이 같은 것인지 확인하기 위해서 저는 다음과 같이 비교해주었습니다.

 

1. 먼저 퍼즐 조각의 모든 위치를 x가 작은 것을 기준으로 정렬하고 만약 같다면 y가 작은 것을 기준으로 정렬해주었습니다.

 

2. 정렬된 퍼즐 조각의 가장 첫 번째 위치를 서로 비교하여 그 차이를 더해주고 비교했습니다.

 

만약 아래와 같은 두 퍼즐이 있다고 가정하면 정렬을 해주면 1. [00,10,20,21] 2. [11,21,31,32] 가 될 것 입니다.

 

ex) 1. 00 10 20        2. 11 21 31

                     21                      32

 

두 퍼즐의 가장 첫 번째 즉 00과 11의 차이는 0 - 1 = -1 0 - 1 = -1  -1,-1이므로

 

두번째 퍼즐의 x와 y에 -1,-1을 더해주면 첫 번째 퍼즐과 같이 될 것 입니다.

 

그리곤 모든 퍼즐의 위치를 비교해줍니다.

 

func checkEqualPuzzleCount() -> Int {
    var answer:Int = 0
    while !emptyBlocks.isEmpty {
        let empty = emptyBlocks.removeFirst()
        outer:for (i,block) in blocks.enumerated() {
            if block.count != empty.count { continue }
            let emptySort = sortBlock(block: empty)
            second:for rotateBlock in rotateBlocks(block: block) {
                var rotateSort = sortBlock(block: rotateBlock)
                let x = emptySort.first!.0 - rotateSort.first!.0
                let y = emptySort.first!.1 - rotateSort.first!.1
                rotateSort = rotateSort.map{($0.0+x,$0.1+y)}
                for i in 0..<emptySort.count {
                    if emptySort[i] != rotateSort[i] {
                        continue second
                    }
                }
                    blocks.remove(at: i)
                    answer += empty.count
                    break outer
            }
        }
    }
    return answer
}

 

 

4. 같은 퍼즐의 조각들을 세어 반환합니다.

 

 return checkEqualPuzzleCount()

---

Source Code

 

	import Foundation
	var boardCopy:[[Int]] = []
	var emptyBlocks:[[(Int,Int)]] = []
	var blocks:[[(Int,Int)]] = []
	func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
	boardCopy = game_board
	findBlocks(isEmpty:true)
	boardCopy = table.map{$0.map{abs($0-1)}}
	findBlocks(isEmpty:false)
	return checkEqualPuzzleCount()
	}
	func findBlocks(isEmpty:Bool) {
	var check:Bool = true
	while check {
	check = false
	outer:for (y,board) in boardCopy.enumerated() {
	for (x,n) in board.enumerated() {
	if n == 0 {
	if isEmpty {
	emptyBlocks.append([(x,y)])
	}else {
	blocks.append([(x,y)])
	}
	boardCopy[y][x] = 1
	makePuzzle(x: x, y: y,isEmpty: isEmpty)
	check = true
	break outer
	}
	}
	}
	}
	}
	func makePuzzle(x:Int,y:Int,isEmpty:Bool) {
	var queue:[(Int,Int)] = [(x,y)]
	while !queue.isEmpty {
	let first = queue.removeFirst()
	let new = [(first.0-1,first.1),(first.0+1,first.1),(first.0,first.1-1),(first.0,first.1+1)]
	for d in new {
	if 0..<boardCopy.count ~= d.0 && 0..<boardCopy.count ~= d.1 {
	if boardCopy[d.1][d.0] == 0 {
	boardCopy[d.1][d.0] = 1
	if isEmpty {
	emptyBlocks[emptyBlocks.count-1].append(d)
	}else {
	blocks[blocks.count-1].append(d)
	}
	queue.append(d)
	}
	}
	}
	}
	}
	func checkEqualPuzzleCount() -> Int {
	var answer:Int = 0
	while !emptyBlocks.isEmpty {
	let empty = emptyBlocks.removeFirst()
	outer:for (i,block) in blocks.enumerated() {
	if block.count != empty.count { continue }
	let emptySort = sortBlock(block: empty)
	second:for rotateBlock in rotateBlocks(block: block) {
	var rotateSort = sortBlock(block: rotateBlock)
	let x = emptySort.first!.0 - rotateSort.first!.0
	let y = emptySort.first!.1 - rotateSort.first!.1
	rotateSort = rotateSort.map{($0.0+x,$0.1+y)}
	for i in 0..<emptySort.count {
	if emptySort[i] != rotateSort[i] {
	continue second
	}
	}
	blocks.remove(at: i)
	answer += empty.count
	break outer
	}
	}
	}
	return answer
	}
	func rotateBlocks(block:[(Int,Int)]) -> [[(Int,Int)]] {
	var newBlock = block
	var rotateBlocks:[[(Int,Int)]] = [block]
	for _ in 0..<3 {
	var rotateBlock:[(Int,Int)] = []
	for b in newBlock {
	rotateBlock.append((b.1,-b.0))
	}
	newBlock = rotateBlock
	rotateBlocks.append(rotateBlock)
	}
	return rotateBlocks
	}
	func sortBlock(block:[(Int,Int)]) -> [(Int,Int)] {
	let sort:[(Int,Int)] = block.sorted{$0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0 }
	return sort
	}

view raw 퍼즐 조각 채우기.swift hosted with ❤ by GitHub