파이썬으로 풀어보는 백준 2580번: 스도쿠

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

내 풀이:

field = [list(map(int, input().split())) for _ in range(9)]
check = [False] * 27    # 가로줄 9개, 세로줄 9게, 사각형 9개에 대한 체크리스트 27개
line_check = [False] * 10    # 0자리도 포함하여 1부터 9까지 이미 사용한 숫자를 체크하기 위한 리스트
 
while False in check:
    for i, horizontal_TF in enumerate(check[0:9]):    # horizontal_TF 는 n번 째 가로줄이 완성되있는가를 True, False로 표기
        if horizontal_TF:
            continue
 
        if field[i].count(0) == 0:
            check[i] = True
            continue
 
        if field[i].count(0) == 1:
            for _ in range(9):
                line_check[field[i][_]] = True
 
            field[i][field[i].index(0)] = line_check.index(False)
            check[i] = True
            line_check = [False] * 10
        else:
            pass
 
    for i, verticle_TF in enumerate(check[9:18]):   # verticle_TF 는 n번 째 세로줄이 완성되있는가를 True, False로 표기
        if verticle_TF:
            continue
        count_zero = 0
        for _ in range(9):
            if field[_][i] == 0:
                count_zero += 1
 
        if count_zero == 0:
            check[i + 9] = True
            continue
 
        if count_zero == 1:
            t = 0
            for _ in range(9):
                line_check[field[_][i]] = True
                if field[_][i] != 0:
                    t += 1
                else:
                    tt = t
            field[tt][i] = line_check.index(False)
            check[i+9] = True
            line_check = [False] * 10
        else:
            pass
 
    for i, square_TF in enumerate(check[18:]):    # square_TF 는 n번 째 3*3이 완성되있는가를 True, False로 표기
        if square_TF:
            continue
 
 
        count_zero = 0
        for y in range(i // 3 * 3, i // 3 * 3 + 3):
            for x in range(i % 3 * 3, i % 3 * 3 + 3):
                if field[y][x] == 0:
                    count_zero += 1
 
        if count_zero == 0:
            check[i + 18] = True
            continue
 
        if count_zero == 1:
            t = 0
            for y in range(i // 3 * 3, i // 3 * 3 + 3):
                for x in range(i % 3 * 3, i % 3 * 3 + 3):
                    line_check[field[y][x]] = True
                    if field[y][x] != 0:
                        t += 1
                    else:
                        tt = t
            field[i // 3 * 3 + tt // 3][i % 3 * 3 + tt % 3] = line_check.index(False)
            check[i + 18] = True
            line_check = [False] * 10
 
        else:
            pass
 
for _ in range(9):
    print(" ".join([str(i) for i in field[_]]))

Python3, 시간 초과

가로줄, 세로줄, 사각형의 순서로 0이 존재하는가 존재하지 않는가를 기준으로 확인하였으며 한번 확인된 가로줄, 세로줄, 사각형은 다시는 확인해보지 않도록 코딩하였으나 시간이 초과하였다. 시간을 줄이는 방법은 그동안의 경험을 미루어봤을 때 2중, 3중 for문이 존재한다면 가장 안쪽에 있는 조건문을 어떠한 방법을 통해서 최대한 for문 바깥쪽으로 넘기는 것이다.

 

[문제] 만약 모든 행, 열, 혹은 사각형에서 0이 2개 이상이라면 이 알고리즘으로는 스도쿠를 완성할 수 없다.

 

다시 풀어본 스도쿠 문제

https://conak-diary.tistory.com/86

백준 2580번: 스도쿠