[프로그래머스 Level2] [1차] 프렌즈4블록 Python

📝문제 설명

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

🚩해결방안

• 주어진 2차 board 리스트를 열과 행을 바꾸어 사용
• bfs로 풀어 현위치+DELTA=[(0, 0), (1, 0), (0, 1), (1, 1)]를 각각 검사하여 모두 블록이 같은 블록이면 2x2 정사각형 삭제할 블록이 될수 있다.
• 주어진 줄에 삭제할 블록을 0으로 바꾸고 해당 줄마다 0의 갯수를 세어 empty=해당개수*['x']를 만든다.
• empty리스트를 왼쪽에 채워넣고 그 뒤에는 아직 삭제되지 않은 블록이나 이미 아까삭제되어 'x'인 블록 리스트를 붙여넣는다.
  (왼쪽에서 채워 넣는 이유는 리스트의 열과 행을 처음에 바꾸었기때문에 위가 아닌 왼쪽에서 적용)

✔ 문제풀이

---

def bfs(m, n, board):
    x, y=0, 0
    DELTA=[(0, 0), (1, 0), (0, 1), (1, 1)]
    del_info=set()
    # bfs search
    while True:
        for i in range(4):
            dy, dx = DELTA[i]
            if board[y][x]!=board[y+dy][x+dx] or board[y][x]=='x':
                break
        else:
            del_info.add((y, x))
            del_info.add((y+1, x))
            del_info.add((y, x+1))
            del_info.add((y+1, x+1))

        if x+1 == m-1 and y+1 != n-1:
            x=0
            y+=1
        elif x+1 < m-1:
            x+=1
        elif y+1 == n-1:
            break

    # board_set
    for y, x in del_info:
        board[y][x]=0
    # board_update
    for i, row in enumerate(board):
        empty=['x']*row.count(0)
        board[i]=empty+[block for block in row if block!=0]

    return len(del_info)

def solution(m, n, board):
    cnt = 0
    b=list(map(list,zip(*board)))

    while True:
        # bfs로 정사각형 4개 모양의 블록 찾기
        del_cnt=bfs(m, n, b)
        if del_cnt==0: # 더 이상 삭제 시킬 것이 없음
            return cnt
        cnt+=del_cnt

---