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

chanyeong kim·2021년 12월 23일

목록 보기

36/51

📩 -->문제설명

프렌즈4블록

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

💡 solution(사용언어: python)

# board에서 2x2 이상이 같으면 팡팡으로 바꿔주는 함수
def find(m,n,board):
    tmp=[]
    cnt=0 # 팡팡의 갯수를 세주기 위해서    
    for i in range(m-1):
        for j in range(n-1):
            if board[i][j]!=board[i][j+1]:
                continue
            else:
                if board[i+1][j]==board[i][j] and board[i+1][j+1]==board[i][j] and board[i][j]!='팡팡':
                    tmp.append([i,j])
    for i in tmp:
        a=i[0]
        b=i[1]
        board[a][b]='팡팡'
        board[a+1][b]='팡팡'
        board[a][b+1]='팡팡'
        board[a+1][b+1]='팡팡'
    
    board=list(zip(*board))
    board=list(map(list, board))
    new_board=[]
    for i in board:
        new_board.append(sorted(i, key=lambda x: -len(x)))
    new_board=list(zip(*new_board))
    new_board=list(map(list, new_board))
    
    return new_board
    
# 더이상 팡팡이 나오지 않을때까지 find 함수를 돌린 후 팡팡의 개수를 리턴
def solution(m, n, board):
    board=list(map(list, board))
    answer=find(m,n,board)
    if answer!=board:
        while True:
            if answer==find(m,n,answer):
                break
            else:
                answer=find(m,n,answer)
    cnt=0
    for i in answer:
        for j in i:
            if j=='팡팡':
                cnt+=1
    return cnt

👉 설명

find는 board에서 2x2 이상의 블록들이 같으면 팡팡으로 바꾸어주는 함수이다.
solution은 팡팡으로 바뀐 board가 find가 리턴해주는 것과 같을 때까지 find를 실행시키고 while문을 빠져나왔을 때 answer의 cnt 갯수를 리턴해주는 것이다.
기본적인 아이디어는 같은 블록들이 있다면 왼쪽 위를 찾아주는 것이었다.
board에서 2x2가 같은 애들의 왼쪽 위의 위치를 tmp에 담아주었다.
tmp에 있는 애들 기준으로 2x2인 애들을 팡팡으로 바꾸어 주었다.
이후 길이로 정렬을 한 후 팡팡인 애들을 리스트 맨 앞으로 가져왔다.(다시 팡팡 터트릴려고!)
한번 find를 거쳐나온 board가 새로 find를 거친 것과 같았을 때의 팡팡 갯수를 리턴해주면 된다!