[Programmers] [1차] 프렌즈4블록

 

 

 

[문제 설명]

 

 

프렌즈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)을 의미한다

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

 

 

 

 

 

 

[풀이 과정]

 

 

카카오 코딩테스트 문제는 언제나 어렵다. 하지만 문제가 묻는 바 또한 명확하고 머리를 싸매서 분투하다 보면 풀 수 있을 만한 문제로 구성되어 있다. 

 

지금의 문제 또한 역시 그렇다. 푸는데에 50분은 넘게 걸린 것 같았는데 풀고나니 참 상쾌하고 좋다.

 

여튼! 문제로 들어가보자.

 

배열 형태에서 2x2 블록이 모두 같으면 지워내고 위에 블록은 아래로 떨어뜨린다.

 

배열 형태에서 이를 곧이 곧대로 구현하는 것은 참 피곤할 것 같다 싶어서,

 

 

필자는 잔꾀를 부렸다.

 

 

처음에는 누구나 그러하듯이 2차원 배열 형태로 바꾼다.

 

 

이후 

 

map(list,zip(*)) 을 이용하여 y = -x 를 기준으로 뒤집고, 문자열을 거꾸로 뒤집어 놓으면 

 

2x2모양으로 pop해도 저절로 문자열이 정렬되면서 아래로 떨어뜨려야 하는 수고를 덜 수 있다!

 

 

즉!

 

문제에서 주어진 배열을 뒤집고 돌려서 블록이 떨어져야하는 방향을 세팅해놓고 시작한다!

 

 

이후에는 간단한 2차원 배열 다루기 문제다.  뇨호호호 잔머리 만세!

 

 

def Square(board):
    a = len(board)-1
    data = []
    for i in range(0, a):
        for j in range(0, min(len(board[i]), len(board[i+1]))-1):
            if board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1]:
                data.append((i,j))
                data.append((i,j+1))
                data.append((i+1,j))
                data.append((i+1,j+1))
    return data

def solution(m, n, board):
    board = list(map(lambda x: list(x),board))
    board = list(map(list, zip(*board)))
    board = list(map(lambda x: x[::-1],board))
    
    while True:
        data = Square(board)
        data = sorted(list(set(data)),reverse=True)
        
        if not data:
            return m*n-len(sum(board,[]))
        
        for a,b in data:
            del board[a][b]