[프로그래머스/Lv2] [1차] 프렌즈4블록

문제

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

같은 모양의 카카오프렌즈 블록이 2x2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

 

그림 1

만약 판이 위와 같이 주어질 경우, 라이언이 2x2로 배치된 7개 블록과 콘이 2x2로 배치된 4개 블록이 지워진다.

같은 블록은 여러 2x2에 포함될 수 있으며, 지워지는 조건에 만족하는 2x2 모양이 여러 개 있다면 한꺼번에 지워진다.

 

그림 2

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

 

그림 3

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

 

그림 4

 

위 초기 배치를 문자로 표시하면 다음과 같다.

 

TTTANT

RRFACC

RRRFCC

TRRRAA

TTMMMF

TMMTTJ

 

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

 

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지를 반환하는 함수를 만들어야 한다.

입력으로는 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.

 

 

제한사항

1. n, m은 2 이상 30 이하이다.

2. board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

 

 

코드

def solution(m, n, board):  
    def init_remove(m, n, board_list):
        remove = set()
        for i in range(m-1):
            for j in range(n-1):
                character = board_list[i][j]
                if character == '!':
                    continue
                if board_list[i+1][j] == character and board_list[i][j+1] == character and board_list[i+1][j+1] == character:
                    remove.add((i,j))
                    remove.add((i+1,j))
                    remove.add((i,j+1))
                    remove.add((i+1,j+1))

        return remove

    def set_board_list(m, n, board_list):
        while True:
            check = 0
            for i in range(m-1):
                for j in range(n):
                    if board_list[i][j] != '!' and board_list[i+1][j] == '!':
                        board_list[i+1][j] = board_list[i][j]
                        board_list[i][j] = '!'
                        check = 1
            if check == 0:
                break
            
                                        
    board_list = [list(board[i]) for i in range(m)]

    answer = 0
    while True:
        remove = init_remove(m, n, board_list)

        if remove:
            answer += len(remove)
            for i, j in remove:
                board_list[i][j] = '!'
        else:
            return answer

        set_board_list(m, n, board_list)

 

 

설명

문제를 푸는데 시간이 너무 오래 걸려서 다른 사람이 푼 풀이를 참고해서 풀었다.

 

아래의 방법으로 문제를 풀 것이다.

1. 2x2 형태로 모여있는 같은 모양의 블록의 좌표를 기록해 둔다.

2. 기록해 둔 좌표의 개수를 answer 변수에 저장하고, 해당 좌표의 값들을 !로 바꾼다.

3. !가 기록된 좌표는 비어있는 블록이기 때문에 위 칸이 비어있지 않다면 아래로 떨어드려 준다.

 

def init_remove(m, n, board_list):
    remove = set()
    for i in range(m-1):
        for j in range(n-1):
            character = board_list[i][j]
            if character == '!':
                continue
            if board_list[i+1][j] == character and board_list[i][j+1] == character and board_list[i+1][j+1] == character:
                remove.add((i,j))
                remove.add((i+1,j))
                remove.add((i,j+1))
                remove.add((i+1,j+1))

    return remove

지울 좌표를 기록하여 반환하는 함수이다.

board_list의 최대 폭, 최대 높이의 -1만큼을 검사하는데, 이렇게 동작시키는 이유는

현재 인덱스에서 3칸을 검사할 때, 최대 폭이나 최대 높이에서는 검사할 수 없게 되기 때문이다.

 

그림 1

그림 2

 

그림 3

 

현재 인덱스의 값을 character 변수에 저장하고 위 아래 대각선 3방향의 값들을 character와 비교하여

같다면 2x2 형태의 같은 모양 블록이므로 지울 좌표에 각 좌표들을 기록한다.

 

이때 remove를 set 자료형으로 초기화해둬서 중복된 값이 존재하지 않도록 한다.

 

def set_board_list(m, n, board_list):
    while True:
        check = 0
        for i in range(m-1):
            for j in range(n):
                if board_list[i][j] != '!' and board_list[i+1][j] == '!':
                    board_list[i+1][j] = board_list[i][j]
                    board_list[i][j] = '!'
                    check = 1
        if check == 0:
            break

빈 칸을 없애고 위 블록을 아래로 떨어뜨리는 함수이다.

빈 칸은 '!'로 구분한다.

 

빈 칸이 가장 위로 올 때 까지 반복하게 된다.

 

board_list = [list(board[i]) for i in range(m)]

1차원 배열로 이루어진 board를 2차원 배열로 바꿔 board_list에 저장한다.

 

answer = 0
while True:
    remove = init_remove(m, n, board_list)

    if remove:
        answer += len(remove)
        for i, j in remove:
            board_list[i][j] = '!'
    else:
        return answer

    set_board_list(m, n, board_list)

remove에 지울 좌표가 없을 때 까지 반복한다.

init_remove함수로 remove 변수에 지울 좌표를 기록해둔 배열을 저장한다.

 

remove가 존재한다면 answer에 remove배열의 길이만큼을 더해주고

기록된 좌표들의 위치에 '!'를 기록해 비어있다는 것을 표시한다.

 

set_board_list 함수를 통해 board_list의 빈 칸을 없애고 위 블록들을 떨어뜨려준다.

---

참고 : https://my-coding-notes.tistory.com/226

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