[레벨2] 프렌즈4블록

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

프로그래머스

2018년 카카오 블라인트 리쿠르트 기출 문제이다.

애니팡과 같은 게임을 푸는 코드를 작성하면 된다.

고급 알고리즘을 구현할 필요는 없지만, 머리를 좀 써야하는 문제였다.

나는 다음과 같은 구조로 코드를 작성하였다.

1. 팡 할 부분 탐색

2. 팡

3. 팡해서 빈 부분을 인형으로 채움

4. 더 이상 변화가 없을 때까지 1-3을 반복

 

def solution(m,n,board):
    def play(board):
        board = [list(i) for i in board]

        # "팡 " 할 부분 탐색
        res = []
        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]:
                    res.append((i,j))

        # " 팡 "한 부분을 빈칸으로           
        for (i,j) in res:
            board[i][j] = " "
            board[i+1][j] = " "
            board[i][j+1] = " "
            board[i+1][j+1] = " "

        # 아래가 빈칸이면 내리기
        res = []
        for i in range(n):
            tmp = ""
            for j in range(m):
                tmp += board[j][i]
            res.append(tmp.replace(" ", "").rjust(m))

        new_board = [[" " for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                    new_board[i][j] = res[j][i]
        return new_board
    
    # 모두 팡 할 때까지 반복
    new_board = play(board)
    while board != new_board:
        board = new_board
        new_board = play(board)

    answer = m*n - len("".join(["".join(i) for i in new_board]).replace(" ", ""))
    return answer