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

프렌즈4블록

문제

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

제한 사항

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

풀이

제거할 블럭 묶음 찾기

BFS를 하면서 어떤 (i, j)가 왼쪽 위에 위치하는 2x2 묶음이 있는지 확인한다. 있다면 출발점을 제외한 나머지 3개 블럭을 큐에 넣는다.

지워야하는 블럭들은 모두 checked에 넣어서 반환해줬다.

블럭 내리기

행, 열을 바꿔서 0을 제거한 후 앞에 빈 공간만큼 0을 채워서 다시 리스트로 바꾸고 행, 열도 바꿔줬다.

한 턴을 진행할 때마다 모든 행, 열을 완전 탐색하면서 BFS를 돌리고 지워야할 칸을 0으로 표시해준 후 블럭을 내렸다.

from collections import deque
​
# BFS
def clear(x, y, board, checked):
    m = len(board)
    n = len(board[0])
    
    q = deque([(x, y)])
    while q:
        cx, cy = q.popleft()
        dir_ = [(0, 1), (1, 0), (1, 1)]
        
        if board[cx][cy] != '0':
            tmp = check_2x2(cx, cy, dir_, board)
            if len(tmp) == 3: 
                for t in tmp:
                    if t not in checked:
                        q.append(t)
                        checked.add(t)
        
    return checked
​
# 2 X 2 묶음인지 확인
def check_2x2(x, y, directions, board):
    m = len(board)
    n = len(board[0])
    checked = set()
    for dx, dy in directions:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < m and 0 <= ny < n:
            if board[nx][ny] == board[x][y]:
                checked.add((nx, ny))
        else:
            break
    return checked
​
# 블럭 내리기
def compaction(board):
    m = len(board)
    n = len(board[0])
    
    tmp = [''.join(list(b)) for b in zip(*board)]
    
    for i in range(len(tmp)):
        tmp[i] = tmp[i].replace('0', '')
        tmp[i] = list('0' * (m - len(tmp[i])) + tmp[i])
    
    tmp = [list(t) for t in zip(*tmp)]
    
    return tmp
    
def solution(m, n, board):
    answer = 0
    board = [list(b) for b in board]
    
    while True:
        cnt = 0
        for i in range(m):
            for j in range(n):
                cleared = []
                if board[i][j]  != '0':   
                    cleared = clear(i,j,board, set())
                    if cleared:       
                        # 삭제된 곳 표시
                        board[i][j] = '0'
                        for x, y in cleared:
                            board[x][y] = '0'
                        cnt += len(cleared) + 1
                        
        if cnt > 0 :
            board = compaction(board)   
            answer += cnt
        else:
            break
    return answer