[Programmers] 프렌즈4블록 - Python

 

난이도: Lv. 2

 

📜 문제 설명

---

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

 

예제에 대한 설명

---

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

 

✏️ Solution(솔루션)

---

from collections import defaultdict

def can_bomb_loc(board, now_i, now_j, m, n, loc, now_block, check_loc):
    if now_block == 0:
        return loc
    
    check = [[[-1, 0], [-1, -1], [0, -1]], [[-1, 0], [-1, 1], [0, 1]], 
            [[0, -1], [1, 0], [1, -1]], [[0,1], [1,0], [1, 1]]]

    for c in check:
        temp = []
        for i, j in c:
            ni = now_i + i
            nj = now_j + j
            
            if 0 <= ni < n and 0 <= nj < m and board[ni][nj] == now_block:
                temp.append((ni, nj))
            else:
                break
        
        if len(temp) == 3:
            temp.append((now_i, now_j))
            for i, j in temp:
                if not check_loc[(i, j)]:
                    check_loc[(i,j)] = True
                    loc.append((i,j))
                    
    return loc
    
def solution(m, n, board):
    answer = 0
    new_board = [[] for _ in range(n)]
    
    for i in range(n):
        for j in range(m-1, -1, -1):
            new_board[i].append(board[j][i])

    while True:
        loc = []
        check_loc = defaultdict(bool)

        for i in range(n):
            for j in range(m):
                loc = can_bomb_loc(new_board,i,j, m, n, loc, new_board[i][j], check_loc)
        
        for i, j in loc:
            new_board[i][j] = -1
        
        for i in range(n):
            while -1 in new_board[i]:
                new_board[i].remove(-1)
                new_board[i].append(0)
                
        answer+=len(loc)
        
        if len(loc) == 0:
            break
        
    return answer

 

실행 결과

---

 

코드 설명

---

 

이 문제는 위 그림과 같이 조건에 맞는 2x2 모양 블록을 지우고 더 이상 지울 수 있는 블록이 없을 때까지 이를 반복한다.

 

이 과정에서 지워지는 블록의 수를 return하면 되는 구현 문제였다.

 

이 문제를 해결하기 위해서는 블록을 지우면 지워진 블록 위에 있던 블록들은 아래로 내려오게끔 구현을 해야한다.

 

이를 위해 아래 그림과 같이 board를 돌려 주었다.

 

이렇게 하면 각 행을 리스트로 판단했을 때, 지울 수 있는 요소를 지우면 자동으로 앞으로 붙을 수 있다.

즉, 지워진 블록 위에 있던 블록들이 아래로 내려온다고 생각할 수 있다.

 

그 후, 각 요소별로 인접한 위치에 블록들을 확인하여 지워질 수 있는지 확인해야한다.

총 4가지의 경우의 수가 있는데 다음과 같다.

 

각 위치별로 이 경우의 수를 확인해 지워질 수 있으면 지워질 수 있는 위치를 저장하는 함수인 can_bomb_loc을 구현했다.

예를 들어, 위 그림의 경우 2번의 경우가 조건에 만족해 지워질 수 있다. 따라서 (2,2), (1,2), (1,3), (2,3)의 위치를 저장했다.

 

또한, 이렇게 저장하다보면 중복되는 위치가 있을 수 있기 때문에 중복을 확인하여 저장했다.

 

모든 요소를 돌아 지워야하는 위치를 모두 구했으면, 이 위치를 -1 값으로 바꿔주고, remove 함수를 통해 -1을 지워주었다.

 

이를 완료하면 위 그림과 같이 board가 업데이트 된다.

board에 빈 부분은 0으로 채워주어 board의 길이를 유지해주었다.

 

이러한 과정을 블록을 지울 수 없을 때까지 반복하고, 반복하면서 count한 지워진 블록의 수를 정답으로 return 하였다.

---

이 문제는 어떠한 알고리즘을 적용하여 푸는 문제는 아니었지만, 구현이 좀 빡셌던 것 같다.

이러한 빡구현 문제에 대해서도 공부할 필요가 있을 것 같다.

 

[Programmers] 프렌즈4블록 - Python

프로그래머스