[알고리즘] 카카오 - [1차] 프렌즈4블록 Python

이 문제 포스팅할 생각이 없었는데, 생각보다 테스트케이스 5번과 10번에 대해 어려움을 겪는 사람들이 많은것 같아서 포스팅해보려구 합니다 ㅎㅎ (저도 5번, 10번 통과가 안되어서 뭐가 문제인지 헤멨어요 ㅜㅜ)

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

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

문제는 위와 같은 격자 배열에서, 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임입니다. 해당 블록이 사라지면 위에 있던 블록은 아래로 내려오게 됩니다. (이때 또 위와 같은 조건을 만족하면 블록이 사라지고 점수를 얻고 반복!)

많은 분들이 풀어보고 방문하셨을거라 생각되기 때문에, 자세한 예시와 문제 설명은 위 문제 링크를 들어가서 확인 바랍니다 :)

접근 방법)

1. 조건(블록이 2×2 형태로 4개가 붙어있는 경우)에 부합하는 인덱스 찾기 & 집합에 추가 

2. 집합 개수를 answer에 더하기, 집합을 순회하면서, 해당 인덱스를 '0'으로 변환 (공백을 의미)

3. board의 밑(맨 하단 행)부터 위로 올라가면서 큐를 사용해 공백을 만나면 큐에 해당 인덱스를 넣고, 카카오 프렌즈를 만나면 큐에서 공백위치를 pop해서 해당 위치에 카카오 프렌즈 넣기 & 원래 카카오 프렌즈 위치 '0'으로 변환(공백으로 변환) & 큐에 넣어주기

프로그래머스 질문하기에 사람들이 올려놓은 테스트케이스 다 통과하는데도 5, 10이 안되는분들 계실텐데요. (저 포함 ㅎㅎ) 사람들 말대로 바로 위 프렌즈만 내리는게 아니라 모든 프렌즈를 다 내려준다고 생각하고 있었거든요. 근데 한가지 빼먹은게, 원래 프렌즈가 있던 위치에서 내려오게 되면 그 자리에도 공백이 생기는데 그 공백에 대한 처리를 안해주다보니 테스트 케이스 5, 10이 통과가 안되는거였더라구요. 

테스트 케이스를 m = 8, n = 2, board = ["CC", "BB", "AA", "BB", "BB", "AA", "BB", "CC"] 로 잡고 테스트 해보세요. 정답이 맞아도 매번 board를 재배열하고나서 print를 찍어 확인해보면 조금 이상한걸 확인할 수 있을거에요!

다음은 전체 코드입니다. 

읽어주셔서 감사합니다 :) 

파이썬 코드

import collections 

def solution(m, n, board):
    answer = 0
    check_set = set()
    board = list(map(lambda x: list(x), board))
    
    # 2x2 블록 조건에 맞는지 확인 후, 조건에 부합할 시 집합에 해당 인덱스를 추가하는 함수
    def check(b):
        for i in range(m-1):
            for j in range(n-1):
                if b[i][j] == b[i+1][j] == b[i][j+1] == b[i+1][j+1] != '0':
                    check_set.add((i,j))
                    check_set.add((i+1,j))
                    check_set.add((i,j+1))
                    check_set.add((i+1,j+1))
    
    # 격자를 다시 재배열하는 함수 
    def arrange(b):
        for j in range(len(b[0])):
            q = collections.deque([])
            
            # 격자의 밑에서부터 탐색
            for i in range(len(b)-1,-1,-1):
                if b[i][j] == '0':
                    q.append((i,j)) 
                else:
                    if q:
                        qi, qj  = q.popleft()
                        b[qi][qj] = b[i][j]
                        b[i][j] = '0'
                        # 테스트 케이스 5, 10을 통과하려면 해당 아이템이 밑으로 내려와서 
                        # 공백이 생기는것 도 고려 해줘야 합니다.
                        q.append((i, j)) 
    
    while True:
    	# check 함수를 통해 공백이 생기는곳 위치(인덱스) 기록
        check(board)
        
        # 만약 공백이 있다면
        if check_set:
       		# 공백 기록
            for i, j in check_set:
                board[i][j] = '0'
            # 답에 공백 갯수 추가
            answer += len(check_set)
            # 공백을 기록했으니, 격자 재배열
            arrange(board)
            # 다음 기록을 위해 집합 비우기
            check_set.clear()
        # 공백이 없다면
        else:
        # 더 이상 점수를 얻을수 없으니 반복문 탈출
            break
    
    return answer