개발/algorithm

[프로그래머스][level2] [1차] 프렌즈4블록 - python

zzi_on2 2022. 4. 14. 22:30

문제 링크

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

 

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

프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙

programmers.co.kr

 

풀이 

1. 행과 열 뒤집기 

 

2. 제거된 블록의 개수 세어주기 

- 이전에 블록들이 제거돼서 블록이 없는 부분은 -1로 표시하고, 현 시점에 제거 될 수 있는 블록은 0 으로 표시 

1) 그래프를 확인하면서 4개의 블록으로 묶여서 사라질 수 있으면 0으로 표시 

2) 0의 개수를 세어서 제거될 블록의 개수 계산 

3) 제거된 블록의 수 만큼 -1로 채우고, 아직 제거안된 블록들로 채우기 

4) 갱신된 그래프과 제거된 0의 개수 리턴 

 

3. 제거된 블록의 개수가 0이라면 더이상 제거될 블록이 없다는 것이므로 정답 리턴 

    제거된 블록이 있다면 블록 수 더하기 

import copy 

def remove(graph, m, n):
    # 제거된 블록개수 
    pops = 0
    
    # 제거된 블록 수 체크할 배열 
    tmp =  copy.deepcopy(graph)
    
    for i in range(1,n):
        for j in range(1,m):
            # 블록이 없는 곳이면 넘어가기  
            if graph[i][j] == -1:
                continue 
            # 사라질 수 있으면 
            if graph[i][j] == graph[i-1][j] == graph[i][j-1] == graph[i-1][j-1]:
                # 0으로 채워넣기 
                tmp[i][j], tmp[i-1][j], tmp[i][j-1], tmp[i-1][j-1] = 0,0,0,0
    
    for i, v in enumerate(tmp):
        # 0 의 개수세기 
        cnt = v.count(0)
        pops += cnt 
        # 위에 있던 블록들 떨어뜨려주기 
        tmp[i] = [-1] * cnt + [ a for a in v if a!= 0] 
                
    return tmp, pops 
    
def solution(m, n, board):
    answer = 0 
    # 행과 열 뒤집기 
    graph = list(map(list, zip(*board)))

    while True:
        graph, pops = remove(graph,m,n)
        # 더이상 제거될 블록이 없으면 
        if pops == 0 :
            return answer 
        # 제거된 블록 수 더하기 
        answer += pops