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

문제 확인

프로그래머스

나의 풀이

• 제거할 (2 x 2) 박스를 찾기 위해서, 박스의 왼쪽 상위 좌표를 기준으로 완전 탐색했다.
• 박스 안에 제거할 좌표가 중복되는 것을 방지하기 위해 set 자료형을 활용했다.
• 제거할 좌표의 성분은 0으로 바꿔주고, 블록을 순회하여 0을 가장 위로 보냈다. 

# (2 x 2) -> 한번에 제거 -> 판별을 어떻게 할 것인지???
# 왼쪽 상위 좌표 [i, j] 기준 완전 탐색
# 제거된 후 블럭이 내려옴 -> 어떻게 처리 -> 열 별로 맵 탐색 -> 0 나오면 swap...

def solution(m, n, board):
    board = list(map(list, board))
    cnt = 0
    # 2 x 2 블록의 왼쪽 상위 좌표 탐색
    # 제거할 수 없을 때 까지 반복
    while True:
        # 제거할 박스 정보 저장
        hit_box = set()
        for i in range(m - 1):
            for j in range(n - 1):
                lt, ld, rt, rd = board[i][j], board[i + 1][j], board[i][j + 1], board[i + 1][j + 1]
                # 제거할 블록인지 확인
                # 이미 빈 칸인 경우 개수 세지 않음
                if lt == ld == rt == rd and lt != 0:
                    hit_box.add((i, j))
                    hit_box.add((i + 1, j))
                    hit_box.add((i, j + 1))
                    hit_box.add((i + 1, j + 1))
        # 더 이상 제거될 블록이 없다면 종료
        if not hit_box: break
        # 제거한 블록 개수 더하기
        cnt += len(hit_box)
        # 블록 제거
        for hit in hit_box:
            hit_i, hit_j = hit
            board[hit_i][hit_j] = 0
        # 블록 이동 : 열 단위로 진행
        for j in range(n):
            # 0일 경우 swap
            for i in range(m):
                for ii in range(1, m - i):
                    if board[ii][j] == 0:
                        # 맨 위로 보내기 위해서 [ii -1] 과 [i]를 swap
                        board[ii - 1][j], board[ii][j] = board[ii][j], board[ii - 1][j]
    return cnt

다른 사람 풀이

• 블록을 편하게 다루기 위해서 행-열을 변경했다.
• 제거된 블록을 위로 보내기 위해서 [0] * 제거된 블록의 개수 + [제거 X 블록] 방식을 활용했다.

# 파이썬
def pop_num(b, m, n):
    pop_set = set()
    # search
    for i in range(1, n):
        for j in range(1, m):
            if b[i][j] == b[i-1][j-1] == b[i-1][j] == b[i][j-1] != '_':
                pop_set |= set([(i, j), (i-1, j-1), (i-1, j), (i, j-1)])
    # set_board
    for i, j in pop_set:
        b[i][j] = 0        
    # 0을 맨 위로 변경하기
    for i, row in enumerate(b):
        empty = ['_'] * row.count(0)
        b[i] = empty + [block for block in row if block != 0]
    return len(pop_set)
     
def solution(m, n, board):
    count = 0
    # 행 - 열 바꾸기
    b = list(map(list,zip(*board)))
    while True:
        pop = pop_num(b, m, n)
        if pop == 0: return count
        count += pop

 

프렌즈 4블록 - 2018 카카오 공채 (python)