글 읽기 - 2580 스도쿠문제 시간 초과 개선

iviolin2003 2년 전 0

제 코드의 개선할 곳이 어디인지 궁금합니다.

구글링해서 나온 코드들을 실행시켜보면 0이 많은 케이스에 대해서는 제 코드보다 답을 출력하는데 오랜 시간이 걸렸습니다.

그런데 구글링해서 나온 코드들은 pypy3로 제출하니 성공이라는 코드가 많았습니다.

그렇기에 제 코드도 pypy3로도 제출해봤지만 시간초과 였습니다.

제 코드는 한 단계마다 0의 해당 위치에서 가질 수 있는 수들을 계속 찾고 그 숫자들을 하나씩 대입해보는 코드라고 보면 됩니다.

어디를 손보면 스도쿠문제를 통과할 수 있을까요?

import sys

Sdoku = []
zero_count = 0

def find_value(i, j, array):

    find_3_3 = set()
    find_row = set()
    find_column = set()
    temp_3_3 = []
    temp_column = []

    for x in range(1, 10):
        temp_column.append(array[x-1][j])
        if x not in array[i]:
            find_row.add(x)
    
    for x in range(1, 10):
        if x not in temp_column:
            find_column.add(x)

    for x in range((i//3) * 3, ((i+3)//3) * 3):
        for y in range((j//3) * 3, ((j+3)//3) * 3):
            temp_3_3.append(array[x][y])

    for x in range(1, 10):
        if x not in temp_3_3:
            find_3_3.add(x)

    return find_3_3 & find_row & find_column

def Check_Row(val, i, array):
    
    if val not in array[i]:
        return True
    else: return False

def Check_Column(val, j, array):
    Column_temp = []
    for x in range(len(array)):
        Column_temp.append(array[x][j])
    
    if val not in Column_temp:
        return True
    else: return False

def Check_3_3(val, i, j, array):
    Check_temp_3_3 = []
    for x in range((i//3) * 3, ((i+3)//3) * 3):
        for y in range((j//3) * 3, ((j+3)//3) * 3):
            Check_temp_3_3.append(array[x][y])
    if val not in Check_temp_3_3:
        return True
    else: return False

def DFS_Sdoku(array):
    global zero_count

    sort_explore_value = []
    explore_value = {}
    len_count = 0
    remove_temp = []

    if zero_count == 0:
        for line in array:
            print(*line)
        exit(0)

    else:
        for i in range(9):
            for j in range(9):
                if array[i][j] == 0:
                    temp = list(find_value(i, j, array))
                    explore_value[str(10*i+j)] = temp
                    
        for k in explore_value.items():
            if  len(k[1]) == 0:
                len_count += 1

        if len_count == 0:
            for k in sorted(explore_value, key=lambda k: len(explore_value[k])):
                sort_explore_value.append(k)
            for num in sort_explore_value:
                remove_temp = explore_value[num].copy()
                for val in explore_value[num]:
                    if Check_Row(val, int(num)//10, array):
                        if Check_3_3(val, int(num)//10, int(num) % 10, array):
                            if Check_Column(val, int(num) % 10, array):
                                array[int(num)//10][int(num) % 10] = val
                                zero_count -= 1
                                DFS_Sdoku(array)
                                zero_count += 1
                                array[int(num)//10][int(num) % 10] = 0
                                remove_temp.remove(val)
                                if len(remove_temp) == 0:
                                    return

for _ in range(9):
    line_temp = [v for v in map(int, sys.stdin.readline().strip().split())]
    Sdoku.append(line_temp)

for i in range(9):
    zero_count += Sdoku[i].count(0)

DFS_Sdoku(Sdoku)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2580 스도쿠문제 시간 초과 개선

iviolin2003 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말