[프로그래머스 / 파이썬] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT)

 

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

 

문제 설명

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

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

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

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

위 초기 배치를 문자로 표시하면 아래와 같다.

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

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

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

 

풀이

 

문제가 굉장히 길지만, 특별한 알고리즘을 요구하는 문제가 아니다.

정사각형 모양으로만 블록이 사라지므로 BFS나 DFS도 필요하지 않다.

다만, 아래 그림과 같이 정사각형이 서로 겹칠 가능성이 있다.

 

 

필자의 경우 어차피 블록은 무조건 2x2의 정사각형 모양이어야 터질 수 있으니 아래 그림과 같이 m-1, n-1의 범위만 탐색하며 진행해나갔다.

 

그리고 정사각형 모양의 4블록이 탐색된다면 좌표만 집합에 기록해두고 다음 블록으로 넘어간다.

집합에 기록한다면 중복은 남지 않으므로, 겹치는 부분을 쉽게 해결할 수 있다.

 

끝까지 진행했다면, 집합에 있는 원소의 수만큼 블록이 터졌을 것이므로 집합의 길이만큼 카운트에 추가한다.

그리고 집합에 있는 좌표대로 보드에서 블록을 없애준다.

 

이제 블록이 위에서 내려오는 것만 진행해주면 된다.

만약 해당 자리에 블록이 있고, 밑에는 블록이 없다면 밑으로 당겨준다.

반복하다가 더 이상 움직여지지 않는 때가 온다면, break으로 탈출한다.

 

그리고 위의 과정을 반복한다.

만약 블록이 한 개도 터지지 않았다면 터진 블록의 개수를 리턴한다.

 

def solution(m, n, board):
    for i in range(m):
        board[i] = list(board[i])
    
    cnt = 0
    rm = set()
    while True:
        # 보드를 순회하며 4블록이 된 곳의 좌표를 집합에 기록
        for i in range(m-1):
            for j in range(n-1):
                t = board[i][j]
                if t == []:
                    continue
                if board[i+1][j] == t and board[i][j+1] == t and board[i+1][j+1] == t:
                    rm.add((i,j));rm.add((i+1,j))
                    rm.add((i,j+1));rm.add((i+1,j+1))
        
        # 좌표가 존재한다면 집합의 길이만큼 세주고 블록을 지움 
        if rm:
            cnt += len(rm)
            for i,j in rm:
                board[i][j] = []
            rm = set()
        # 없다면 함수 종료
        else:
            return cnt
        
        # 블록을 위에서 아래로 당겨줌
        while True:
            moved = 0
            for i in range(m-1):
                for j in range(n):
                    if board[i][j] and board[i+1][j]==[]:
                        board[i+1][j] = board[i][j]
                        board[i][j] = []
                        moved = 1
            if moved == 0:
                break