[PRO] 블록 게임

정답까지 총 2시간 소요된 문제이다.

처음 작성한 스켈레톤 코드는 다음과 같다.

ans = float('-inf')
N = None

def delete_block(board, will_delete_block):
    global N
    
    new_board = [item[:] for item in board]
    for x in range(N):
        for y in range(N):
            if new_board[x][y] == will_delete_block:
                new_board[x][y] = 0
                
    return new_board

def dfs(now_board, deleted_block_num):
    global ans
    ans = max(ans, deleted_block_num)
    
    # TODO 제거할 수 있는 블록 리스트 목록
    can_delete_blocks = []
    
    for will_delete_block in can_delete_blocks:
        # 해당 블록 제거한 새 board 생성
        new_board = delete_block(now_board, will_delete_block)
        dfs(new_board, deleted_block_num+1)


def solution(board):
    global ans,N
    
    N = len(board)
    dfs(board, 0)
    
    return ans

이후 경우의 수를 따져서 TODO 부분을 채운 코드는 다음과 같다.

ans = float('-inf')
N = None

def is_valid(now_board,x,y,check_num):
    if 0<=x<N and 0<=y<N and now_board[x][y]==check_num:
        return True
    return False
        

def delete_block(board, will_delete_block):
    global N
    
    new_board = [item[:] for item in board]
    for x in range(N):
        for y in range(N):
            if new_board[x][y] == will_delete_block:
                new_board[x][y] = 0
                
    return new_board

def dfs(now_board, deleted_block_num):
    global ans
    ans = max(ans, deleted_block_num)
    
    # TODO 제거할 수 있는 블록 리스트 목록
    can_delete_blocks = set()
    for y in range(N):
        for x in range(N):
            block_num = now_board[x][y]
            if block_num: # 0이면 빈곳
                # 모양 체크
                # type1의 3번째(가장 오른쪽기준)
                if is_valid(now_board,x,y-1,block_num) and is_valid(now_board,x,y-2,block_num)\
                and is_valid(now_board,x-1,y-2,block_num) and is_valid(now_board,x-1,y-1,0):
                    can_delete_blocks.add(block_num)
            
                # type1의 4번째(가장 왼쪽기준)
                if is_valid(now_board,x,y+1,block_num) and is_valid(now_board,x-1,y+1,block_num)\
                and is_valid(now_board,x-2,y+1,block_num):
                    can_delete_blocks.add(block_num)
                
                # type2의 2번째(가장 오른쪽기준)
                if is_valid(now_board,x,y-1,block_num) and is_valid(now_board,x-1,y-1,block_num)\
                and is_valid(now_board,x-2,y-1,block_num):
                    can_delete_blocks.add(block_num)
                
                # type2의 3번째(가장 왼쪽기준)
                if is_valid(now_board,x,y+1,block_num) and is_valid(now_board,x,y+2,block_num)\
                and is_valid(now_board,x-1,y+2,block_num) and is_valid(now_board,x-1,y+1,0):
                    can_delete_blocks.add(block_num)
                
                # type3의 1번째(가장 왼쪽 기준)
                if is_valid(now_board,x,y+1,block_num) and is_valid(now_board,x-1,y+1,block_num)\
                and is_valid(now_board,x,y+2,block_num) and is_valid(now_board,x-1,y+2,0):
                    can_delete_blocks.add(block_num)
                
                break
                
    can_delete_blocks = list(can_delete_blocks)
    
    for will_delete_block in can_delete_blocks:
        # 해당 블록 제거한 새 board 생성
        new_board = delete_block(now_board, will_delete_block)
        dfs(new_board, deleted_block_num+1)


def solution(board):
    global ans,N
    
    N = len(board)
    dfs(board, 0)
    
    return ans

이때 시간 초과와 실패가 섞여서 뜬다. 시간 초과의 원인은 board를 매번 새로 만들어주는 부분인 것 같아서 보드를 매번 새로 만드는게 아닌 삭제된 블록번호면 빈 곳과 같이 처리되도록 바꿨는데도, 동일하게 시간 초과가 섞여서 떴다.

ans = float('-inf')
N = None
g_board = None

def is_valid(x,y,check_num, deleted_set):
    global g_board
    
    if 0<=x<N and 0<=y<N:
        # deleted_set 포함된건 0과 같이 되도록
        board_num = g_board[x][y]
        if board_num in deleted_set:
            board_num = 0
            
        if board_num == check_num:
            return True
        
    return False

def dfs(deleted_block_num, deleted_set):
    global ans, g_board
    ans = max(ans, deleted_block_num)
    
    # TODO 제거할 수 있는 블록 리스트 목록
    can_delete_blocks = set()
    for y in range(N):
        for x in range(N):
            block_num = g_board[x][y]
            if block_num and block_num not in deleted_set: # 0이면 빈곳
                # 모양 체크
                # type1의 3번째(가장 오른쪽기준)
                if is_valid(x,y-1,block_num,deleted_set) \
                and is_valid(x,y-2,block_num,deleted_set)\
                and is_valid(x-1,y-2,block_num,deleted_set) \
                and is_valid(x-1,y-1,0,deleted_set):
                    can_delete_blocks.add(block_num)
            
                # type1의 4번째(가장 왼쪽기준)
                if is_valid(x,y+1,block_num,deleted_set) \
                and is_valid(x-1,y+1,block_num,deleted_set)\
                and is_valid(x-2,y+1,block_num,deleted_set):
                    can_delete_blocks.add(block_num)
                
                # type2의 2번째(가장 오른쪽기준)
                if is_valid(x,y-1,block_num,deleted_set) \
                and is_valid(x-1,y-1,block_num,deleted_set)\
                and is_valid(x-2,y-1,block_num,deleted_set):
                    can_delete_blocks.add(block_num)
                
                # type2의 3번째(가장 왼쪽기준)
                if is_valid(x,y+1,block_num,deleted_set) \
                and is_valid(x,y+2,block_num,deleted_set)\
                and is_valid(x-1,y+2,block_num,deleted_set) \
                and is_valid(x-1,y+1,0,deleted_set):
                    can_delete_blocks.add(block_num)
                
                # type3의 1번째(가장 왼쪽 기준)
                if is_valid(x,y+1,block_num,deleted_set) \
                and is_valid(x-1,y+1,block_num,deleted_set)\
                and is_valid(x,y+2,block_num,deleted_set) \
                and is_valid(x-1,y+2,0,deleted_set):
                    can_delete_blocks.add(block_num)
                
                break
                
    can_delete_blocks = list(can_delete_blocks)
    
    for will_delete_block in can_delete_blocks:
        # 해당 블록 제거한 새 board 생성
        # deleted_set will_delete_block 더한 새로운 set 저장
        new_deleted_set = set(deleted_set)
        new_deleted_set.add(will_delete_block)
        dfs(deleted_block_num+1, new_deleted_set)


def solution(board):
    global g_board, ans, N
    g_board = board
    N = len(g_board)
    dfs(0, set())
    
    return ans

저번에 mutable을 함수 파라미터로 넘길때 모든 곳에서 다 수정이 일어났던 경우를 생각해서 deepcopy해준건 잘한 것 같다.

DFS로 파고 들어갈때 항상 O(N^2)인게 문제라고 느꼈고, DFS안에서 O(N^2)이 안되도록 수정을 시도했다.

아 제거할 수 있으면 항상 다 제거하면 되는거였다. 제거하는 순서는 중요하지 않았다. 최대라는 말에 집착해서 모든 경우의 수를 생각한 것 같다.

제거 가능하면 항상 제거하도록 해서 시간초과는 사라졌는데, 실패가 아직 섞여있다.

원인은 모양을 체크할때 위가 뻥 뚫렸는지 체크하는걸 생략했기 때문이다.
질문하기 탭의 반례를 통해 찾을 수 있었는데 반례가 없었으면 못 찾았을 수도 있을 것 같다.
반례를 너무 빨리 체크한 것 같은데 다음에는 조금 더 고민하고 체크해야겠다.

정답코드는 아래와 같다. 경우의 수를 체크하는 부분을 최적화할 수 있을 것 같다.

N = None
g_board = None

def is_valid(x,y,check_num, deleted_set):
    global g_board
    
    # index out check
    if not (0<=x<N and 0<=y<N):
        return False
    
    # 0인지 확인할때는 위가 다 뚫렸는지 체크
    if check_num == 0:
        for test_x in range(x):
            if g_board[test_x][y] not in deleted_set and g_board[test_x][y]:
                return False
    
    # deleted_set 포함된건 0과 같이 되도록
    board_num = g_board[x][y]
    if board_num in deleted_set:
        board_num = 0
    
    if board_num == check_num:
        return True
        
    return False


def solution(board):
    global g_board, N
    g_board = board
    N = len(g_board)
    ans = 0
    
    can_delete_flag = True
    deleted_set = set()
    while can_delete_flag: #제거 가능한게 있으면
        can_delete_flag = False
        for y in range(N):
            for x in range(N):
                block_num = g_board[x][y]
                if block_num and block_num not in deleted_set: # 0이면 빈곳
                    # 모양 체크
                    # type1의 3번째(가장 오른쪽기준)
                    if is_valid(x,y-1,block_num,deleted_set) \
                    and is_valid(x,y-2,block_num,deleted_set)\
                    and is_valid(x-1,y-2,block_num,deleted_set) \
                    and is_valid(x-1,y-1,0,deleted_set):
                        can_delete_flag = True
                        deleted_set.add(block_num)
                        ans+=1

                    # type1의 4번째(가장 왼쪽기준)
                    elif is_valid(x,y+1,block_num,deleted_set) \
                    and is_valid(x-1,y+1,block_num,deleted_set)\
                    and is_valid(x-2,y+1,block_num,deleted_set):
                        can_delete_flag = True
                        deleted_set.add(block_num)
                        ans+=1

                    # type2의 2번째(가장 오른쪽기준)
                    elif is_valid(x,y-1,block_num,deleted_set) \
                    and is_valid(x-1,y-1,block_num,deleted_set)\
                    and is_valid(x-2,y-1,block_num,deleted_set):
                        can_delete_flag = True
                        deleted_set.add(block_num)
                        ans+=1

                    # type2의 3번째(가장 왼쪽기준)
                    elif is_valid(x,y+1,block_num,deleted_set) \
                    and is_valid(x,y+2,block_num,deleted_set)\
                    and is_valid(x-1,y+2,block_num,deleted_set) \
                    and is_valid(x-1,y+1,0,deleted_set):
                        can_delete_flag = True
                        deleted_set.add(block_num)
                        ans+=1

                    # type3의 1번째(가장 왼쪽 기준)
                    elif is_valid(x,y+1,block_num,deleted_set) \
                    and is_valid(x-1,y+1,block_num,deleted_set)\
                    and is_valid(x,y+2,block_num,deleted_set) \
                    and is_valid(x-1,y+2,0,deleted_set):
                        can_delete_flag = True
                        deleted_set.add(block_num)
                        ans+=1
                    
                    break # 최상단 체크 완료했으므로
    
    return ans