[프로그래머스] 파이썬 _ 프렌즈4블록 (2018 KAKAO BLIND)

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

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

 

문제유형 : 그래프(행렬다루기), 구현, 완전탐색 

 

문제풀이 :

• 그래프에서 특정위치를 다루고 이런문제가 카카오에서 많이 나오는거같음
• 주어진 보드위에서 정사각형을 움직여가며 모두같아 없어지는경우 집합에 인덱스를 저장한다.
  • 겹치는 구간이 있을수 있으므로 전체를 모두 확인하고 지워야하는 인덱스를 중복없이 저장하기위해 집합을 이용한다.
• 한 라운드에서 모두 탐색이 끝나면 집합에 저장된 위치를 이제 없애줘야햐는데 이때 배열에서 중간원소를 먼저 삭제하면 나머지 인덱스의 위치가 앞으로 떙겨지므로 내가원하는값이 지워지는게 아니라 하나더 뒤에것이 지워져버리게된다.
  • for문의 대상이되는 iterable한 객체를 그 포문안에서 조작하는경우!!!
  • 그렇기 때문에 항상 마지막것이 먼저 지워지게 하기위해서 집합을 리스트로 한번 변환하고, sorting을 통해서 항상 뒤에것부터 지워지도록해서 인데스 변화가 없도록 만든다.
• 더이상 없어질수있는 경우가 없을때, 인덱스를 저장하는 집합의 원소가 없을때 재귀호출을 종료한다.

 

정답코드 :

import sys
sys.setrecursionlimit(10**6)
def solution(m, n, board):
    # 행 - m
    # 열 - n
    global answer
    answer = 0
    graph = [[] for _ in range(n)]
    
    for i in range(n):
        for line in board[::-1]:
            graph[i].append(line[i])
    #print(graph)
    round(graph,n,m)
    #print(answer)
    return answer
    # 보드의 전체를 탐색한다. 
    # 보드위에서 정사각형을 움직이면서 모두 같은경우 해당 인덱스를 집합에 넣어 저장
    # 한 라운드에서 모두 탐색이 끝나면 마지막에 한번에 지운다.
    # 지워지는 블록의 개수를 저장한다.
    # 지운 보드 결과를 재귀로 호출한다.
    # 만약 더이상 4각형이 만들어지지 않으면 재귀를 끝내도록한다.
    
def round(graph,n,m):
    global answer, board
    space = set()
    for i in range(m-1):
        for j in range(n-1):
            temp = []
            # 시작꼭지점의 위치: (i, j)
            for line in graph[j:j+2]:
                temp.append(line[i:i+2])
            if all_same(temp):
                space.add((i,j))
                space.add((i,j+1))
                space.add((i+1, j))
                space.add((i+1, j+1))
    
    # space에 있는 위치를 모두 지운다.
    if len(space)==0:
        return
    answer += len(space)
    
    space = list(space)
    space = sorted(space, key=lambda x:x[0], reverse=True)
    for i,j in space:
        graph[j].pop(i)  # 중간것을 먼저지우면 내가원하는 인덱스에 값이 바뀌므로 소팅후에 지운다.
        
    
    for line in graph:
        while len(line) < m:
            line.append("X")    # 인덱스에러 방지를 위해 지워진값은 쓰레기값으로 채워넣는다.
    #print(graph)    
    round(graph,n,m)
    

def all_same(graph):     # 모든값이 같은지 확인한다.
    if graph[0][0] != graph[0][1]:
        return False
    elif graph[1][0] != graph[1][1]:
        return False
    elif graph[0][0] != graph[1][0]:
        return False
    elif graph[0][0] == 'X':   # 쓰레기값으로 4개가 같은경우 무시한다.
        return False
    return True