Algorithm/Implementation

[프로그래머스 / python / Level 2] 프렌즈4블록

양선규 2025. 6. 13. 00:46
728x90
반응형

문제

 

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 시뮬레이션 문제이고 블럭을 떨어뜨리는 로직을 구현하는 것이 핵심이다.

 

def solution(m, n, board):
    
    """블럭을 제거하는 함수"""
    def delete_blocks(m, n, board):
        
        # 모든 블럭에 대하여 삭제 조건 검사
        deleted_blocks = set()
        for x in range(m - 1):
            for y in range(n - 1):
                
                point = board[x][y]
                if point == '':
                    continue
                
                # 2*2 영역이 같은 블럭이라면 삭제 블럭 집합에 추가
                if (board[x][y] == board[x+1][y] == board[x][y+1] == board[x+1][y+1] == point):
                    for i in range(2):
                        for j in range(2):
                            deleted_blocks.add((x+i, y+j))
        
        # 블럭 삭제
        for x, y in deleted_blocks:
            board[x][y] = ''
        
        # 삭제한 블럭 개수 리턴
        return len(deleted_blocks)
    
    """블럭을 떨어뜨리는 함수"""
    def drop_blocks(m, n, board):
        
        # 열(Column) 단위로 진행
        for y in range(n):
            
            # 비어있지 않은 모든 블럭을 수집
            blocks = []
            for x in range(m):
                if board[x][y] != '':
                    blocks.append(board[x][y])
                    board[x][y] = ''
            
            # 아래쪽부터 역순으로 배치
            x_idx = m - 1
            while len(blocks) > 0:
                board[x_idx][y] = blocks.pop()
                x_idx -= 1
    
    """메인 로직"""
    # board를 2차원 리스트 형태로 변환
    board = [list(row) for row in board]
    
    result = 0
    while True:
        
        # 더이상 블록을 제거할 수 없다면 종료
        count = delete_blocks(m, n, board)
        if count == 0:
            break
        
        # 제거한 블록 개수 갱신
        result += count
        
        # 블록 떨어뜨리기
        drop_blocks(m, n, board)
    
    return result

 

문제에 주어진 내용을 그대로 구현하면 된다. 완전탐색을 진행하면 되며, 최대 30 * 30이기 때문에 시간 초과 날 걱정은 없다.

 

모든 블럭을 기준으로 2*2 공간을 전부 다 검사하여 제거한다. 단 제거할 블럭을 검사하는 것과 삭제하는 로직은 분리해야 한다. 찾자마다 제거해 버리면 여러 공간에 포함된 블럭이 먼저 제거되어 버려 다음 검사되는 블럭은 제거되지 않을 수 있다. 따라서 제거할 블럭을 전부 찾은 후에 제거는 따로 진행한다.

 

그리고 블럭을 떨어뜨리는 로직을 구현해야 한다. 행이 아닌 열 단위로 진행하되, 열에 존재하는 모든 블럭을 수집 후 가장 아래쪽부터 차례대로 배치하면 된다. 중력을 구현하는 가장 간단한 방법이다.

 

이렇게 완성된 제거+떨어뜨리기 2가지를 while문으로 반복하며 제거한 블록의 개수를 세고, 더 이상 제거할 수 없을 때 while문을 종료하면 해결할 수 있다.

728x90
반응형