[BOJ] 2239 스도쿠

검사해야 할 것들은 주어진 좌표의 가로줄, 세로줄 그리고 스도쿠 판을 9개로 나누었을때 속해있는 그 칸의 9개의 나머지 블럭들 이 3가지입니다.

사실 그냥 시간을 전혀 신경쓰지않는다면 간단하게 정답을 구할 수 있지만 문제의 경우는 다음이라고 생각했습니다.

# 이것만 오래 안걸리면 나머지 다 맞을듯
'''
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
'''

 위의 테스트 케이스만 빠르게 해결할 정도라면 문제를 맞추는 것은 어렵지 않다고 생각했고, 이것으로 계속 테스트를 해보았습니다.

 

sector=[[] for i in range(9)]

for x in range(9):
    for y in range(9):
        sector[3*(y//3)+x//3].append((x,y))

0	1	2
3	4	5
6	7	8

일단 이렇게 9개의 좌표값을 갖는 구역 0~8까지를 만들어주었습니다.

 

이 구역을 활용해서 이 위치에 들어올수 있는 값들의 배열을 얻는 함수를 만들어주었습니다.

def check(x,y):
    to_check=[1]*10
    for X,Y in sector[3*(y//3)+x//3]:
        to_check[sdoku[Y][X]]=0

    for l in range(9):
        to_check[sdoku[l][x]]=0
        to_check[sdoku[y][l]]=0 
    return to_check

크기가 10(1+9)인 배열을 만들어주고 같은 x,  같은y 그리고 같은 sector에 속해있는 값들을 비교해서 들어올수 없는 값의 위치를 0으로 바꾸어 준 뒤 배열을 전달해주었습니다.

def dfs(x):
    X,Y=locate[x]
    able=check(X,Y)
    for i in range(1,10):
        if able[i]==1:
            sdoku[Y][X]=i
            dfs(x+1)
            sdoku[Y][X]=0

이제 dfs로 가능한 배열들을 돌려주기만 하면 됩니다!

import sys
input=sys.stdin.readline

sdoku=[list(map(int,input().split())) for i in range(9)]
sector=[[] for i in range(9)]

for x in range(9):
    for y in range(9):
        sector[3*(y//3)+x//3].append((x,y))

def dfs(x):
    X,Y=locate[x]
    able=check(X,Y)
    for i in range(1,10):
        if able[i]==1:
            sdoku[Y][X]=i
            dfs(x+1)
            sdoku[Y][X]=0
            
def check(x,y):
    to_check=[1]*10
    for X,Y in sector[3*(y//3)+x//3]:
        to_check[sdoku[Y][X]]=0

    for l in range(9):
        to_check[sdoku[l][x]]=0
        to_check[sdoku[y][l]]=0 
    return to_check

locate=[]
for i in range(9):
    for j in range(9):
        if sdoku[i][j]==0:
            locate.append((j,i))
try:
    dfs(0)
except:
    for i in range(9):
        print(*sdoku[i])

dfs를 진행하다 만약 x값이 너무 커지게 되면 오류가 나고, 그 시점에는 이미 스도쿠가 완성되어 있으므로 출력해주었습니다.

이 문제를 한 달전에 제가 풀었었더라고요,,

오늘,

한달전

코드도 엄청 짧아지고 시간도 많이 빨라진 것을 보니 기분이 좋네요 ㅎㅎ

 

pypy3기준 백트래킹으로 풀 경우 걸리는 시간이라 적혀있는데, 같은 코드를 제출했을 때 파이썬은 84%에서 시간 초과가 나는데 고칠 방법을 모르겠네요 ㅠ..