소프티어

안녕하세요.

예시 입력들이 통과해서 제출했는데 테스트 케이스 중 절반 정도 오답이 나왔네요.

반례 케이스가 어떤게 있을까요??

import sys

def getColor(square):
    square2lists = []
    for r in range(N):
        for c in range(N):
            square2lists.append([square[r][c], [r, c]])

    results = set()
    for square2list in square2lists:
        cur_r = square2list[1][0]
        cur_c = square2list[1][1]

        shouldIpass = 0
        for result in results:
            if (cur_r, cur_c) in result[1]:
                shouldIpass = 1
        if shouldIpass == 1:
            continue
    
        total_list = set()
        total_list.add((cur_r, cur_c))
        visited = set()
        visited.add((cur_r, cur_c))
        
        dr = [0, 0, -1, 1]
        dc = [-1, 1, 0, 0]
        
        queue = []
        queue.append(square2list)        
        while queue:
            color, curr = queue.pop(0)
            r, c = curr
            for i, j in zip(dr, dc):
                nr = r + i
                nc = c + j
                if 0 <= nr < N and 0 <= nc < N:
                    if (nr, nc) not in visited:
                        visited.add((nr, nc))
                        if square[nr][nc] == color:
                            queue.append([color, [nr, nc]])
                            total_list.add((nr, nc))
                            
        total_num = len(total_list)
        if total_num == 1:
            continue
        
        r_min = r_max = cur_c
        c_min = c_max = cur_c
        for tmp_list in total_list:
            if tmp_list[0] <= r_min:
                r_min = tmp_list[0]
            if tmp_list[0] >= r_max:
                r_max = tmp_list[0]
            if tmp_list[1] <= c_min:
                c_min = tmp_list[1]
            if tmp_list[1] >= c_max:
                c_max = tmp_list[1]

        area_rectangular = (r_max - r_min + 1)*(c_max - c_min + 1)
        total_score = total_num + area_rectangular
        
        results.add((total_score, tuple(total_list)))
    return results

def removeSquare(square, storage, delete_list):
    tmp_square = list(map(list, zip(*square)))
    tmp_storage = [x[:] for x in storage]
    for r in range(N):
        for c in range(N):
            if (c, r) in delete_list:
                del tmp_square[r][c]
                tmp = tmp_storage[r].pop()
                tmp_square[r].insert(0, tmp)
    square = list(map(list, zip(*tmp_square)))
    return square, tmp_storage

N = int(input())
data = [list(map(int, input().split())) for _ in range(3 * N)]
storage = list(map(list, zip(*data)))

tmp_square = []
for c in range(N):
    row = []
    for _ in range(N):
        tmp = storage[c].pop()
        row.insert(0, tmp)
    tmp_square.append(row)

square = list(map(list, zip(*tmp_square)))

# first try
results = getColor(square)

max_score = 0

for result in results:
    first_square, first_storage = removeSquare(square, storage, result[1])
    
    if result[0] > max_score:
        max_score = result[0]

    # second try
    second_results = getColor(first_square)

    for second_result in second_results:
        second_square, second_storage = removeSquare(first_square, first_storage, second_result[1])

        if result[0] + second_result[0] > max_score:
            max_score = result[0] + second_result[0]

        # third try
        third_results = getColor(second_square)

        for third_result in third_results:
            if result[0] + second_result[0] + third_result[0] > max_score:
                max_score = result[0] + second_result[0] + third_result[0]

print(max_score)