[Programmers] 프렌즈4블록 (Python3)

문제

프렌즈4블록
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 “프렌즈4블록”.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ
각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

입력으로 판의 높이 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|

문제풀이

카카오 문제들은 풀 때마다 까다로운 것 같다. 이 문제도 푸는데 너무 오랜시간이 걸렸다.
근데 논리 구조가 조금 까다로워서 그렇지, 사실 어려운 발상을 하거나 특정 알고리즘을 적용할 필요는 없는 문제였는데 자꾸 브루트포스말고 신박한 풀이를 생각해내려다 더욱 오래 걸렸다. 항상 시간복잡도를 생각해보고, 시간복잡도 신경 안써도 되겠다 싶은 문제면 그냥 브루트포스로 풀어버리는게 결국 더 문제를 빨리 푸는 방법인것 같다.

코드

def solution(m, n, boards):
    #board를 이차원 배열로 받는 리스트 board
    board_list = []
    
    #board를 이차원 배열로 받는다.
    for board in boards:
        board_list.append(list(board))
    
    
    
    #오른쪽, 아래, 오른쪽 아래 대각을 확인할 dx,dy
    dx = [1,0,1]
    dy = [1,1,0]
    
    count = 0
    
    
    while 1:
        #삭제여부를 0과 1로 나타낼 리스트 remove
        remove = [[0 for i in range(n)]for i in range(m)]
        
        for i in range(m):
            for j in range(n):
                if board_list[i][j] == '-':
                    continue
                for k in range(3):
                    nx = i+dx[k]
                    ny = j+dy[k]
                    if 0<= nx < m and 0<= ny < n:
                        if board_list[i][j] != board_list[nx][ny]:
                            break
                    else:
                        break
                else:
                    remove[i][j] = 1
                    for k in range(3):
                        nx = i+dx[k]
                        ny = j+dy[k]
                        remove[nx][ny] = 1
                    
        if max(map(max,remove))== 0:
            break
            
        for i in range(m):
            for j in range(n):
                if remove[i][j] == 1:
                    board_list[i][j] = '-'
                    count+=1
        while 1:      
            check = []
            for i in range(m):
                for j in range(n):
                    if board_list[i][j] == '-':
                        if i-1 >= 0 and board_list[i-1][j] != '-' :
                            board_list[i][j] = board_list[i-1][j]
                            board_list[i-1][j] = '-'
                            check.append(1)
            if len(check) == 0:
                break
            
    return count

solution(8, 5, ['HGNHU', 
                'CRSHV', 
                'UKHVL', 
                'MJHQB', 
                'GSHOT', 
                'MQMJJ', 
                'AGJKK', 
                'QULKK'])

8