야도란의 아무말 블로그
알고리즘 연습 [프렌즈 4블록]

카카오 공채 1-6 프렌즈 4블록

문제

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 “프렌즈4블록”.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

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

입출력 예제
m	n	board	answer
4	5	[“CCBDE”, “AAADE”, “AAABF”, “CCBBF”]	14
6	6	[“TTTANT”, “RRFACC”, “RRRFCC”, “TRRRAA”, “TTMMMF”, “TMMTTJ”]	15
예제에 대한 설명
입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

나의 풀이

def block_game(m, n, board):
    count = 0
    for i, s in enumerate(board):
        board[i] = list(s)

    def remove(m, n, board):
        temp = []
        for i in range(m - 1):
            for j in range(n):
                for k in range(j + 2, n + 1):
                    if board[i][j] == board[i][k - 1] != ' ' and board[i][j:k] == board[i + 1][j:k]:
                        temp.append([i, j, k])
        if len(temp) == 0:
            return
        else:
            for t in temp:
                board[t[0]][t[1]] = ' '
                board[t[0] + 1][t[1]] = ' '
                board[t[0]][t[2] - 1] = ' '
                board[t[0] + 1][t[2] - 1] = ' '

            for i in range(m - 1, 1, -1):
                for j in range(n):
                    k = i - 1
                    while board[i][j] == ' ' and k > -1:
                        board[i][j] = board[k][j]
                        board[k][j] = ' '
                        k -= 1
            print(board)
            remove(m, n, board)

    remove(m, n, board)

    for i in range(m):
        for j in range(n):
            if board[i][j] == ' ':
                count += 1

    return count


print(block_game(4, 5, ['CCBDE', 'AAADE', 'AAABF', 'CCBBF']))
print(block_game(6, 6, ['TTTANT', 'RRFACC', 'RRRFCC', 'TRRRAA', 'TTMMMF', 'TMMTTJ']))
© 2018 Yadoran. All rights reserved.