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

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

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

 

다른 접근으로 푼 게 아니라서 시간 초과에 걸리지 않을까 했는데 정답이 됐다.

 

1) board 행렬을 돌면서 사라지는 블록 4개의 좌표를 set 에 담는다.

 

2) set 에 있는 좌표에 해당하는 board 의 값을 '0' 으로 바꿔주고 해당하는 열의 행 값을 한 칸 아래로 내린다. '0' 은 맨 위로 올려 board 를 다시 설정한다. 이때, 이 작업을 좌표의 오름차순으로 진행해야 하는데 set 이 정렬이 안 되므로 list 로 변화시켜준 후 sorted 하여 작업을 진행한다.

 

3) 이러한 과정을 반복하는데, set 에 값이 안 담기는 경우는 더 사라질 블록이 없다는 의미로 answer(+= len(set)) 을 반환한다. 

 

def solution(m, n, board):
    answer = 0
    board = list(map(lambda x : list(x), board))
    
    while True:
        block = set()
        
        for i in range(m-1):
            for j in range(n-1):
                if board[i][j] == board[i+1][j] == board[i][j+1] == board[i+1][j+1] != '0':
                    block.add((i, j))
                    block.add((i+1, j))
                    block.add((i, j+1))
                    block.add((i+1, j+1))
        
        if len(block) == 0:
            break
        else:
            answer += len(block)
        
        for i, j in sorted(list(block)):
            for k in range(i, -1, -1):
                if board[k][j] == '0': break
                
                board[k][j] = '0' if k == 0 else board[k-1][j]
                      
    return answer

print(solution(4, 5, ['CCBDE', 'AAADE', 'AAABF', 'CCBBF'])) # 14