[프로그래머스] 프렌즈 4블록

https://school.programmers.co.kr/learn/courses/30/lessons/17679

프로그래머스

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 

이번에 출시할 게임 제목은 "프렌즈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가 사용된다.

---

풀이

블록이 없어지면 다시 채워주는 과정을 쉽게 생각하기 위해 보드를 시계방향으로 90도 돌려 생각했다.

이렇게 하면 조금 더 직관적으로 보인다.

 

로직

1. 입력받은 board를 시계방향으로 90도 돌리기
2. 회전한 보드에서 제거할 블록들 찾기
3. 블록 제거하며 제거된 블록 수 카운트
4. 제거되는 블록이 없을때까지 반복

 

초기 코드

# 초기 코드
def solution(m, n, board):
    answer = 0
    arr = []
    for x in range(n):
        char = []
        for y in range(m):
            char.append(board[m - y - 1][x])
        arr.append(char)
    directions = [(1, 0), (0, 1), (1, 1)]
    while True:
        visited = set()
        row = len(arr)
        for y in range(row - 1):
            col = len(arr[y])
            for x in range(col - 1):
                character = arr[y][x]
                temp_arr = [(y, x)]
                for dy, dx in directions:
                    ny = y + dy
                    nx = x + dx
                    if (
                        0 <= ny < row
                        and 0 <= nx < len(arr[ny])
                        and arr[ny][nx] == character
                    ):
                        temp_arr.append((ny, nx))
                if len(temp_arr) == 4:
                    for ny, nx in temp_arr:
                        visited.add((ny, nx))
        for y, row in enumerate(arr):
            arr[y] = [value for x, value in enumerate(row) if (y, x) not in visited]
        if not visited:
            break
        answer += len(visited)
    return answer
# 92.57ms, 10MB

상당히 보기 힘들어서 각 로직에 따라 모듈화했다.

사실 처음에 문제를 잘 보지않고 BFS처럼 풀어서 비효율적인 부분도 조금 보인다.

 

1차 수정 : 모듈화

# 1차 수정 : 모듈화
def rotate_board_90(board, m, n):
    rotated = [[None] * m for _ in range(n)]
    for y in range(m):
        for x in range(n):
            rotated[x][m - 1 - y] = board[y][x]
    return rotated

def find_blocks_to_remove(board, m, n):
    to_remove = set()
    for y in range(m - 1):
        for x in range(n - 1):
            if board[y][x] == board[y + 1][x] == board[y][x + 1] == board[y + 1][x + 1] != "":
                to_remove.update({(y, x), (y + 1, x), (y, x + 1), (y + 1, x + 1)})
    return to_remove

def remove_blocks(board, blocks, m, n):
    remove_block_cnt = len(blocks)
    for y, x in blocks:
        board[y][x] = ''
    for y, row in enumerate(board):
        board[y] = [i for i in row if i != '']
        board[y].extend([''] * (n - len(board[y])))
    return remove_block_cnt

def solution(m, n, board):
    rotated_board = rotate_board_90(board, m, n)
    m, n = n, m
    total_removed = 0
    while True:
        blocks = find_blocks_to_remove(rotated_board, m, n)
        if not blocks:
            break
        total_removed += remove_blocks(rotated_board, blocks, m, n)
    return total_removed
# 44.52ms, 10.4MB

모듈화를하니 코드 읽기가 더 수월해졌다. 시간도 50% 이상 단축했다.