[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ [1차] 프렌즈4블록

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

코딩테스트 연습 - [1차] 프렌즈4블록

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

[출력 형식]
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

[아이디어]
1) 맨 마지막에 비어있는 블록의 수가 정답이다. (혹은 터뜨리는 수의 합)
2) 예시의 첫 그림 라이언의 경우처럼 중복되는 것들을 고려하기 위해서는, 삭제 후보를 먼저 모두 탐색한 뒤에 삭제(혹은 변경)를 진행하야한다.
3) 터뜨리는 것들을 0으로 바꾸고, 빈 자리가 생겨 이동할 때는 transpose한 뒤 0의 개수만큼 왼쪽에 0이 있어야 함을 이용하면 좋을 것 같다.

def transpose(board):
    return list( zip(*board))

def check_square(m,n,board):
    empty = set()
    for i in range(m-1):
        for j in range(n-1):
            tmp = board[i][j]
            if tmp == '0':
                pass
            elif (tmp == board[i][j+1] == board[i+1][j] == board[i+1][j+1]):
                empty.add((i,j))
                empty.add((i+1,j))
                empty.add((i,j+1))
                empty.add((i+1,j+1))
    return empty

def shift(board):
    board = transpose(board)
    for i, x in enumerate(board):
        n = x.count('0')
        board[i] = n*'0' + ''.join(x).replace('0', '')
    return transpose(board)

def solution(m, n, board):
    answer = 0
    while True:
        if not check_square(m,n,board):
            return answer
        else:
            answer += len(check_square(m,n,board))
            board = list(map(list, board))
            for i,j in check_square(m,n, board):
                board[i][j] = "0"
            board = shift(board)

다소 복잡하게 푼 감도 있는 것 같다. 터뜨려야 할 위치를 찾는 것은 쉽고, 결국 빈 자리에 맞게 블록을 이동시키는게 문제인데, transpose가 생각대로 되지 않아 좀 헤맸다. zip 함수를 이용해 list를 transpose 하는 것을 좀 기억해두어야겠다. 나는 transpose 이외의 방법을 떠올리지 못했는데, 원 상태에서 3중 for문을 이용해 아래처럼 터진 위치를 채우는 방법을 사용한 사람도 있었다.

for i3 in range(m):
	for i in range(m - 1):
		for j in range(n):
			if x2[i + 1][j] == '팡!':
				x2[i + 1][j], x2[i][j] = x2[i][j], '팡!'

아래가 비었으면 위아래를 바꾸는 것인데, 단순히 m번 반복을 시행함으로써 모든 경우의 수를 커버할 수 있다는 생각을 하지 못했던 것 같다. (사실 알고 봐도 헷갈리고, 좀 비효율적이긴하다.)