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

문제 요약

• 2차원 블록화면이 주어집니다.
• 같은 문자가 사각형 모양으로 4개가 모여있으면 부술 수 있습니다.
• 한 화면에서 부술 수 있는 블록들을 모두 찾은 후, 한번에 부숴야합니다.
• 부술 수 있는 사각형이 겹쳐있는 것을 허용합니다. 단, 부숴진 개수를 셀 때는 겹친 부분을 이중으로 세어선 안됩니다.
• 블럭이 부서진 후엔, 위에 있는 블럭들이 내려옵니다.
• 이 과정을 더이상 블럭이 부서질 수 없을 때까지 반복했을 때, 부서진 블럭의 총 개수를 구하세요.

아이디어

부서지고 위에서 블럭들이 내려온다. 이렇게 변하는 화면 속에서 새로 형성되는 부술 수 있는 블럭을 찾기 위해선 시뮬레이션이 적합하다.

부서질 사각형이 겹쳐져있다

set을 사용해서 지워질 블럭들을 저장한 후, 탐색이 끝나면 한 번에 지워준다.

중력에 의해 블럭이 빈자리를 매꾼다

간단하게 지워져야할 부분을 소문자 'e'로 마킹하고, 마킹된 부분을 제외하고 압축된 열을 만들었다. 그리고 열을 압축된 열로 대체했다.

소스

# 구현, 시뮬
di = [0,1,0,1]
dj = [0,0,1,1]
def in_box(m,n, i,j):
    return i<m and j<n
def seed_check(m,n,board, i, j):
    #사각형의 왼쪽위 기준으로 4개 서치 후 넣기
    if(board[i][j] == 'n'):
        return False
    for ctr in range(1,4):
        ci = i+di[ctr]
        cj = j+dj[ctr]
        if(not in_box(m,n,ci,cj)):
            return False
        if(board[i][j]!=board[i+di[ctr]][j+dj[ctr]]):
            return False
    return True


def one_round(m,n,board):
    s = set()
    for i in range(m):
        for j in range(n):
            if(seed_check(m,n,board, i,j)):
                #지워질 블록들 추가
                for ctr in range(4):
                    s.add((i+di[ctr],j+dj[ctr]))
    return s

def comp_col(m,n,board, j):
    new_col = []# 밑에서부터 축적
    for i in range(m-1, -1,-1):
        if(board[i][j]!='e'):
            new_col.append(board[i][j])
    for i in range(m-1, -1, -1):
        if(len(new_col)==0):
            board[i][j] = 'n'
        else:
            board[i][j] = new_col[0]
            new_col.pop(0)

def solution(m, n, board):
    answer = 0
    for i in range(m):
        board[i] = list(board[i])
    
    while(True):
        s = one_round(m,n,board)
        print(s)
        s = list(s)
        if(len(s)==0):
            break
        answer+=len(s)
        for ctr in range(len(s)):
            board[s[ctr][0]][s[ctr][1]] = 'e'
        for j in range(n):
            comp_col(m,n,board, j)
        
    return answer

모범 소스

def pop_num(b, m, n):
    pop_set = set()
    # search
    for i in range(1, n):
        for j in range(1, m):
            if b[i][j] == b[i - 1][j - 1] == b[i - 1][j] == b[i][j - 1] != '_':
                pop_set |= set([(i, j), (i - 1, j - 1), (i - 1, j), (i, j - 1)])
    # set_board
    for i, j in pop_set:
        b[i][j] = 0
    for i, row in enumerate(b):
        empty = ['_'] * row.count(0)
        b[i] = empty + [block for block in row if block != 0]
    return len(pop_set)


def solution(m, n, board):
    count = 0
    b = list(map(list, zip(*board)))  # 행열 바꿔치기
    while True:
        pop = pop_num(b, m, n)
        if pop == 0: return count
        count += pop