[프로그래머스] 2019 KAKAO BLIND RECRUITMENT Coding Test 블록 게임Solution in Swift

문제 출처

코딩테스트 연습 - 블록 게임

 

---

문제 

  프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다. 이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다. 프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

  아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

  1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

 

  플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다. 

 

  이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

  그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다. 따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

 

  보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

제한사항

• board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.

  • N은 4 이상 50 이하다.

• board의 각 행의 원소는 0 이상 200 이하의 자연수이다.

  • 0 은 빈 칸을 나타낸다.

  • board에 놓여있는 각 블록은 숫자를 이용해 표현한다.

  • 잘못된 블록 모양이 주어지는 경우는 없다.

  • 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.

  • 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

입출력 예

board	result
[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]]	2

입출력 예 설명

입출력 예 #1
문제에 주어진 예시와 같음

 

---

Point

1. 3가지타입의 블럭이 놓여 있는 배열이 있을 때,  1 X 1 블록을 하나씩 떨어뜨려 없앨 수 있는 블록의 최대 개수를 구하는 문제이다.

 

2. 블록은 기존 놓여진 블록의 직사각형 틀 중에 빈 공간을 놓으면 없어진다.

 

---

Solution Tip

블럭의 형태를 확인하여 저장해 놓는다.

각 행의 맨 위쪽에 놓여있는 블럭부터 차례대로 저장된 형태를 가지고 없앨 수 있는지 확인해서 없앤다.

없앤 나머지를 가지고 다시 없앨 수 있는 것을 찾는다.

---

Solution

	//
	// BlockGame.swift
	// ProgrammingProblems
	//
	// Copyright © 2020 roseMelon. All rights reserved.
	//
	import Foundation
	func solution(_ board:[[Int]]) -> Int {
	let vertical: [(Int,Int,Int,Rotate)] = [(-1,1,1,.right),(0,1,3,.right),(1,1,2,.right),(-1,-1,2,.left),(0,-1,3,.left),(1,-1,1,.left)]
	let horizontal: [(Int,Int,Int,Rotate)] = [(-1,-1,1,.up),(-1,0,3,.up),(-1,1,2,.up),(1,-1,2,.down),(1,0,3,.down),(1,1,1,.down)]
	var blocks: [Int: Block] = [:]
	var paddingBoard: [[Int]] = board.map({ [0] + $0 + [0] })
	paddingBoard.insert(Array(repeating: 0, count: board[0].count + 2), at: 0)
	paddingBoard.append(Array(repeating: 0, count: board[0].count + 2))
	var stacked: [[Int]] = []
	for j in 1...board[0].count { // X == j
	var state: [Int] = []
	for i in 1...board.count { // Y == i
	guard paddingBoard[i][j] != 0 else { continue }
	state.append(paddingBoard[i][j])
	let checkV = paddingBoard[i-1][j] == paddingBoard[i][j] && paddingBoard[i+1][j] == paddingBoard[i][j]
	let checkH = paddingBoard[i][j-1] == paddingBoard[i][j] && paddingBoard[i][j+1] == paddingBoard[i][j]
	if checkV || checkH {
	for t in (checkV ? vertical : horizontal) {
	if paddingBoard[i][j] == paddingBoard[i+t.0][j+t.1] && Block.removeable(t.2, t.3) {
	blocks[paddingBoard[i][j]] = Block(center: (i,j), type: t.2, rotate: t.3)
	break
	}
	}
	}
	}
	stacked.append(state)
	}
	var removed = 0
	for _ in 0..<blocks.count {
	let top: [Int] = stacked.map { $0.count > 0 ? $0[0] : 0 }
	let topBlocks: Set<Int> = Set(top.filter { $0 != 0 })
	for topBlock in topBlocks{
	guard let block = blocks[topBlock],
	block.needIndex().count > 0,
	block.needIndex().reduce(true,{ $0 && top[$1-1] == topBlock }) else { continue }
	removed += 1
	stacked = stacked.map { $0.filter { $0 != topBlock } }
	break
	}
	}
	return removed
	}
	struct Block {
	let center: (Int, Int) // (Y, X)
	let type: Int
	let rotate: Rotate
	static func removeable(_ type: Int, _ rotate: Rotate) -> Bool {
	return rotate == .up || (type == 1 && rotate == .left) || (type == 2 && rotate == .right)
	}
	func needIndex() -> [Int] {
	if type == 1 && rotate == .left { return [center.1-1] }
	if type == 1 && rotate == .up { return [center.1, center.1+1] }
	if type == 2 && rotate == .right { return [center.1+1] }
	if type == 2 && rotate == .up { return [center.1-1, center.1] }
	if type == 3 && rotate == .up { return [center.1-1, center.1, center.1+1] }
	return []
	}
	}
	enum Rotate {
	case up, left, right, down
	}

view raw BlockGame.swift hosted with ❤ by GitHub

 

---

2019 카카오 블라인드 채용 코딩 테스트 '블록 게임' 스위프트 솔루션