[프로그래머스] Swift - [1차] 프렌즈 4블록 (LV.2)

👆문제풀러 가기👆

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력형식

 

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

 

입출력 예제

m	n	board	answer
4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

 

풀이 [ 메모리: 16.7mb, 최대시간: 841.52ms ] 

 

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
    let blockType = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".map { String($0) } // 블록 종류
    var board = board.map { String($0).map { String($0) } }         // 전체블록 만들기
    var answer = 0

    while true {
        var beforeBoard = board

        for t in blockType {
            // 블록 타입별 2*2블록 생성
            let doubleSquare = Array(repeating: Array(repeating: t, count: 2), count: 2)
            var memory = Set<[Int]>()

            // 전체 블록에서 2*2사이즈만큼 확인
            for i in 0..<m-1 {
                for j in 0..<n-1 {
                    let up = (doubleSquare[0][0] == board[i][j])
                            && (doubleSquare[0][1] == board[i][j+1])
                    let down = (doubleSquare[1][0] == board[i+1][j])
                            && (doubleSquare[1][1] == board[i+1][j+1])

                    // 2*2블록만큼 일치하면, 해당 블록 위치를 기록.
                    // 같은 위치가 중복 저장되지 않도록 Set 사용.
                    if up && down {
                        memory.formUnion([[i,j], [i,j+1], [i+1,j], [i+1,j+1]])
                    }
                }
            }

            // 블록 지우기
            for r in memory {
                board[r[0]][r[1]] = "-"
                answer += 1
            }
        }
        // 블록을 위에서 아래로 내리는 조건 = 아래에 빈칸이 있어야 한다.
        // 즉, 블록은 아래에서부터 확인해야함.
        for i in stride(from: m-1, through: 0, by: -1) {
            for j in stride(from: n-1, through: 0, by: -1) {
                if (i != 0) && (board[i][j] == "-") {
                    var up = i-1

                    while (up >= 0)  && (board[i][j] == "-") {
                        // 상단블록이 빈블록인지 확인
                        if board[up][j] == "-" {
                            up -= 1
                            continue
                        }
                        // "-"(빈 블록)이 아닌 상단 블록과 교체
                        board[i][j] = board[up][j]
                        board[up][j] = "-"
                    }
                }
            }
        }

        if beforeBoard == board {  break  }
    }

    return answer
}

문제가  다소 짜증난다하여 풀어본 문제인데, 정말 짜증난 문제였다. 

빡구현(?)이라기보단,, 신경쓸게 좀 많았기 떄문.. for문이 하나씩 들어갈 때마다 이렇게까지 반복문을 많이 써야해? 라는 생각을 하게 되는 문제였다. 시간복잡도가 n의 4승이라니..

마치 수능 답지에 마킹하는데 4번이 연속 5번 나온 기분.. 나는 내 풀이가 맞다고 생각하는데, 의심하게 되는 그런 느낌..

 

차근차근 생각해보면,

 

1. 착각하기 쉬웠던 부분은, 카카오 캐릭터 알파벳만 입력되는 것이 아닌, A~Z 대문자 알파벳이 블록에 들어간다는 점.
2. 2*2배열에 A~Z 대문자 알파벳 중 하나를 입력해야 한다는 점.
3. 2*2 배열과 일치하는 좌표를 모두 기억해두고, 한번에 지워야 한다는 점. (즉, 중복 좌표가 생길 수 있으므로 Set으로 중복 제거)
4. 블록이 지워지면, 남은 블록은 위에서 아래로 내려온다는 점.
5. 아래에서부터 위로 블록을 확인하며, 빈 블록이 있으면 윗 블록을 내려서 채운다는 점 등을 고려하고,
6. 위의 과정을 다시 반복했을 때, 이전 블록과 현재 블록이 동일하면, 더 이상 지울 블록이 없다는 것을 의미하므로 종료.

문제 자체가 어렵다기보단 정말,, 피곤했다.