[프로그래머스] 코딩테스트 연습 - [1차] 프렌즈4블록(Python)

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

풀이

해당문제는 특별한 알고리즘이 필요한 것이 아닌 구현 문제였던 것 같습니다.

처음 문제를 풀었던 방식은 board를 그대로 2차원배열로 만들어 사라질 2x2블록을 찾아 위에 남은 블록을 내리는 방식으로 구현하려 했습니다. 그런데 남은 블록을 내리는 기능(열 갱신)을 어떻게 구현할지 생각하다 보니 열을 갱신하는 방법보다 board를 90도 회전시켜서 행을 갱신하는 방법이 더욱 좋을 것 같다는 생각이 들었습니다. slice해서 당겨오거나 새로운 바뀌게 될 행을 새로 만들어 갈아껴주기만하면 되니까요.

 

Code

def solution(m, n, board):
    answer = 0
    bd = list(map(list,zip(*board)))    # board를 회전
    while True:
        coord = set()
        count = 0
        for r in range(n-1):    # 사라질 블록의 좌표 검색
            for c in range(m-1):
                if bd[r][c]==bd[r+1][c]==bd[r][c+1]==bd[r+1][c+1]!='-':
                    tempset = set([(r,c), (r+1,c), (r,c+1), (r+1,c+1)])
                    coord = coord.union(tempset)
                    count += 1
        if count == 0:  # 사라질 블록이 없는 경우
            break
        answer += len(coord)
        for r, c in coord:  # 사라질 블록 표시
            bd[r][c] = '+'
        for row in range(n):    # 새로운 row을 만들어 갱신
            newline = ['-']*bd[row].count('+')
            newline.extend([ele for ele in bd[row] if ele != '+'])
            bd[row] = newline
    return answer

 

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈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