[Python][프로그래머스] level 2 - 프렌즈4블록

문제

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

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈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

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

 

문제이해하기

1. 2 x 2 의 사각형의 문자가 모두 같은 것을 찾는다

2. 찾은 사각형을 없애고 빈공간이 생기면 블록들이 아래로 떨어져 채운다

3. 더이상 사각형을 찾을 수 없을때까지 1, 2를 반복한다

 

풀이과정

1. 계산을 위해 입력값을 2차원배열로 저장한다.
    ["CCBDE", "AAADE", "AAABF", "CCBBF"]    →   [[C, A, A, C], [C, A, A, C], [B, A, A, B], [B, B, D, D], [F, F, E, E]]

2. 2 x 2의 원소들이 모두 같은 경우 각 위치 [x, y] 들을 remove_block 에 저장한다.
3-1. 2의 결과 remove_block이 비어있지 않으면, 3-2가 될때까지 4, 5번을 반복한다.
3-2.                                           비어있으면, while문을 빠져나온다.
4. 지워질 블록들이 담겨있는 remove_block의 길이만큼 answer에 더한다.
5. remove_block의 위치값들을 ""으로 변경하고 ""들을 배열의 가장 뒤쪽으로 이동시킨다. 
※ for block in remove_block 으로 반복문을 돌면서 totalMap의 원소를 remove 하면 인덱스가 꼬여 원하지 않는 결과가 나오기 때문에 원소를 삭제하지 않고 ""로 수정하는 방식으로 구현해야합니다!

Code

remove_block = []
totalMap = []

// 풀이과정 5
def fallBlock(n):
    global remove_block, totalMap
    for block in remove_block:
        totalMap[block[0]][block[1]] = ""
    for i in range(n):
        count = totalMap[i].count("")
        totalMap[i] = [x for x in totalMap[i] if x != ""]
        totalMap[i] += ["" for _ in range(count)]

// 풀이과정 2
def removable(m, n):
    global remove_block, totalMap
    remove_block.clear()
    for x in range(m-1):
        for y in range(n-1):
            if totalMap[x][y] != "" and totalMap[x][y] == totalMap[x][y+1] == totalMap[x+1][y] == totalMap[x+1][y+1]:
                for pair in [[x, y], [x+1, y], [x, y+1], [x+1, y+1]]:
                    if pair not in remove_block:
                        remove_block.append(pair)
    return True if remove_block else False
                        
def solution(m, n, board):
    global totalMap
    // 풀이과정 1
    for x in range(n):
        temp = []
        for y in range(m):
            temp.append(board[m-y-1][x])
        totalMap.append(temp)
        
    answer = 0
    while(removable(n, m)): // 풀이과정 3
        removable(n, m)
        answer += len(remove_block) // 풀이과정 4
        fallBlock(n)
    return answer