[프로그래머스] 프렌즈4블록

 

▼ 문제 링크

코딩테스트 연습 - [1차] 프렌즈4블록

 

우리가 흔히 하는 캔x크러쉬사, 프x즈팝 같은 게임을 구현하는 문제다.
그런데 이제 그 게임에서 블록을 터트릴 수 있는 방법 중, 단 하나, 2x2 블록만 터지도록 설계하면 된다.

STEP1. 2x2 행렬을 살펴보면서 터트릴 블록 찾기

그림1

그림1처럼 2x2 총 4개의 블록이 모두 같은 블록인 경우를 찾아야 한다.
단, 이때 왼쪽의 라이언 블록처럼 2x2가 서로 겹쳐도 상관 없다!

물론, 겹쳐도 상관 없지만 터질 라이언 블록의 총 개수는 4+4가 아니라 겹친 블록 하나를 제외한 4+3 총 7개가 된다.

 

STEP2. 터트린 블록 윗 블록 내리기

그림2

그림2처럼 터진 블록 위에 있는 블록을 내려야 한다.
이때 주의할 점은, 그림2에서 표현한 것과 달리 [빈 공간 | 블록 | 빈 공간] 이런 식으로 블록 중간 중간이 비어있을 수 있다는 점이다.

 

STEP3. 위 과정 반복하기

그림3

2x2 블록을 살펴보고, 터트린 뒤 다시 2x2 블록을 살펴보는 과정을 더 터트릴 블록이 없을 때까지 반복한다.

 

문제를 해결하기 위한 전략을 아래처럼 잡았다.

1. (0, 0)을 시작으로 해당 블록의 우측, 하단, 우하단 블록이 같은 블록인지 확인한다.
1-1. 이 과정은 (0, 0)부터 (m-2, n-2)까지 반복한다.
2. 2x2 블록이 모두 같아 터트릴 블록들은 Set에 입력한다.
2-1. 중복 방지를 위해 Set을 선택
3. Set의 개수를 세어 총 개수에 더한다.
4. 터트릴 블록을 empty문자로 치환한다.
5. 다음 루프를 위해 Set을 초기화 한다
6. 블록을 좌상단부터 살펴보면서 아랫줄이 empty문자면 한줄씩 내린다.
6-1. 이 과정을 더 내릴 블록이 없을 때까지 반복한다.
7. 1번~6번 과정을 터트릴 블록이 나오지 않을 때까지 반복한다.

 

전체 코드

func solution(_ m: Int, _ n: Int, _ board: [String]) -> Int {
	// (mxn) 블록
    var blocks: [[String]] = board.map({$0.map({String($0)})})
    // 한 회차에 한 번이라도 터진 블록들이 존재하는지 여부
    var isPoped: Bool = false
    // 2x2 블록이 모두 동일해 터질 예정인 블록 저장
    var poped: Set<String> = [] // key는 "m,n"
    // 터진 블록의 총 개수
    var total: Int = 0
    // 터지고 빈 공간을 채울 문자
    var empty: String = "#"
    
    // 터트릴 2x2 블록을 탐색하는 함수
    func popBlocks() {
        for i in 0..<m-1 {
            for j in 0..<n-1 {
                let word = blocks[i][j]
                
                if word == empty {
                    continue
                }
                
                if word == blocks[i+1][j] && word == blocks[i][j+1] && word == blocks[i+1][j+1] {
                    poped.insert("\(i),\(j)")
                    poped.insert("\(i+1),\(j)")
                    poped.insert("\(i),\(j+1)")
                    poped.insert("\(i+1),\(j+1)")
                }
            }
        }
        
        if !poped.isEmpty {
            isPoped = true
            total += poped.count
        }
        
        poped.forEach({
            let i = Int($0.components(separatedBy: ",")[0])!
            let j = Int($0.components(separatedBy: ",")[1])!
            
            blocks[i][j] = empty
        })
        
        poped = []
    }
    
    // 터진 블록의 빈 자리 위에 있는 블록을 내리는 함수
    func replaceBlocks() {
        var isMoved: Bool = false
        
        repeat {
            isMoved = false
            
            for i in 0..<m-1 {
                for j in 0..<n {
                    let word = blocks[i][j]

                    if word != empty && blocks[i+1][j] == empty {
                        blocks[i+1][j] = word
                        blocks[i][j] = empty
                        isMoved = true
                    }
                }
            }
        } while isMoved
    }
    
    repeat {
        isPoped = false
        
        popBlocks()
        replaceBlocks()
    } while isPoped
    
    return total
}swift