[프로그래머스] [1차] 프렌즈4블록 - Python

https://programmers.co.kr/learn/courses/30/lessons/17679

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

 

풀이

1. 지워야하는 블록 검사

- check() 함수로 블록이 2x2 형태로 붙어있는지 확인한다.

 

2. 블록 지우기

- popList에 지워질 칸의 행과 열을 저장한다. -> set을 사용하기 위해 튜플 형태로 저장

- set을 사용해 겹치는 부분을 한번만 처리한다.

- 지운 칸은 '-'로 표시한다.

 

3. 블록 내리기

- popList를 내림차순으로 정렬하고, 하나씩 처리한다.

- 지워진 블록이 x행 y열이면, x행부터 위쪽 방향으로 y열에 빈칸이 아닌 블록을 찾아 아래로 내린다.

- 0행까지 반복해서 빈칸을 채운다.

 

4. 재탐색

- 블록을 내리고 지울 블록이 없을 때까지 반복한다.

 

dx, dy = [0, 1, 1], [1, 0, 1]
def check(board, x, y, n, m):    

    for i in range(3):
        nx, ny = x + dx[i], y + dy[i]
        
        if 0 <= nx < m and 0 <= ny < n:
            if board[x][y] != board[nx][ny]:
                return False
    
    return True

def solution(m, n, board):
    answer = 0
    popList = []

    for i in range(m):
        board[i] = list(board[i])    
        
    while True:
        for i in range(m-1):
            for j in range(n-1):
                if board[i][j] == '-': 
                    continue
                    
                if check(board, i, j, n, m):
                    popList.append((i, j))

                    for k in range(3):
                        popList.append((i+dx[k], j+dy[k]))
        
        if len(popList) == 0:
            return answer
        
        popList = sorted(list(set(popList)), reverse=True)
        
        
        # 블록 지우기
        for x, y in popList:
            answer += 1
            board[x][y] = '-'

		
        # 블록 내리기
        for x, y in popList:
            for i in range(x, -1, -1):
                if board[i][y] == '-':
                    for j in range(i-1, -1, -1):
                        if board[j][y] != '-':
                            board[i][y] = board[j][y]
                            board[j][y] = '-'
                            break

        popList = []