[Baekjoon] 2580번 : 스도쿠 (Python, 백트래킹, DFS)

[Baekjoon] 2580번 : 스도쿠 (Python, 백트래킹, DFS)

 

목차

 

 

 

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

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 코드 길이 2182B

 

스도쿠는 행/열/3x3 사각형에 대해서 공통적인 것을 도출하는 문제이다.

하여 이를 고려한 함수를 기반으로 백트래킹을 진행하였으나 시간초과가 나타났다. (Python3, PyPy3 모두 시간초과)

 

def row_ck(x):
    row = [0]*10
    zero = []

    for i in s[x]:
        if i != 0:
            row[i]=1

    for i in range(1, 10):
        if row[i] == 0:
            zero.append(i)

    return zero

def col_ck(y):
    col = [0]*10
    zero = []

    for i in range(9):
        if s[i][y] != 0:
            col[s[i][y]]=1

    for i in range(1, 10):
        if col[i] == 0:
            zero.append(i)

    return zero

def sq_ck(x,y):
    sq = [0]*10
    zero = []

    a, b = x%3, y%3

    for i in range(3):
        for j in range(3):
            if a == 0:
                if b == 0 and s[x+i][y+j] != 0:
                    sq[s[x+i][y+j]] = 1
                elif b == 1 and s[x+i][y+1-j] != 0:
                    sq[s[x+i][y+1-j]] = 1
                elif b == 2 and s[x+i][y-j] != 0:
                    sq[s[x+i][y-j]] = 1
            elif a == 1:
                if b == 0 and s[x+1-i][y+j] != 0:
                    sq[s[x+1-i][y+j]] = 1
                elif b == 1 and s[x+1-i][y+1-j] != 0:
                    sq[s[x+1-i][y+1-j]] = 1
                elif b == 2 and s[x+1-i][y-j] != 0:
                    sq[s[x+1-i][y-j]] = 1
            elif a == 2:
                if b == 0 and s[x-i][y+j] != 0:
                    sq[s[x-i][y+j]] = 1
                elif b == 1 and s[x-i][y+1-j] != 0:
                    sq[s[x-i][y+1-j]] = 1
                elif b == 2 and s[x-i][y-j] != 0:
                    sq[s[x-i][y-j]] = 1

    for i in range(1, 10):
        if sq[i] == 0:
            zero.append(i)

    return zero

def dfs(idx):
    if idx == len(loc):
        res.append(copy.deepcopy(s))
        return

    x, y = loc[idx]
    c = []
    for i in row_ck(x):
        for j in col_ck(y):
            for k in sq_ck(x,y):
                if i == j == k:
                    c.append(i)

    for i in c:
        s[x][y] = i
        dfs(idx+1)
        s[x][y] = 0

import sys
import copy
s = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
visit = [[0]*9 for _ in range(9)]
loc = []
res = []

for i in range(9):
    for j in range(9):
        if not s[i][j]:
            loc.append((i,j))
dfs(0)
for i in res[0]:
    print(' '.join(map(str, i)))

 

시간초과 - 방법 2 - 메모리 145908KB / 시간 3376ms / 코드 길이 891B (PyPy3 통과)

 

방법 1의 경우 공통적인 것을 직접 구해서 비교하고 남은 것들을 토대로 백트래킹을 했다면 방법 2에서는 단순 비교를 진행한다.

0인 위치를 blank list에 저장해서 1~9까지의 숫자를 하나씩 넣어보고 행/열/3x3 사각형에 있는지 없는지 체크하고 된다면 다음 위치로 넘어가는 식으로 진행한다.

방법 1에 비해서는 훨씬 깔끔해진 것을 확인할 수 있다.

 

import sys
s = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
blank = []

for i in range(9):
    for j in range(9):
        if s[i][j] == 0:
            blank.append((i,j))

def row_ck(x, a):
    for i in range(9):
        if a == s[x][i]:
            return False
    return True

def col_ck(y, a):
    for i in range(9):
        if a == s[i][y]:
            return False
    return True

def sq_ck(x, y, a):
    nx, ny = x//3 * 3, y//3*3
    for i in range(3):
        for j in range(3):
            if a == s[nx+i][ny+j]:
                return False
    return True

def dfs(idx):
    if idx == len(blank):
        for i in range(9):
            print(*s[i])
        exit(0)

    for i in range(1, 10):
        x, y = blank[idx]

        if row_ck(x, i) and col_ck(y, i) and sq_ck(x, y, i):
            s[x][y] = i
            dfs(idx+1)
            s[x][y]=  0

dfs(0)

 

 

시간초과 - 방법 3 - 메모리 182288KB / 시간 2568ms / 코드 길이 764B

 

방법 2에서는 행/열/사각형에 대해 별도로 checking하였다면 이 코드에서는 한 번에 체크하고 그 후보군을 활용하는 방법이다.

시간이 단축한만큼 더 많은 메모리 활용이 있다.

 

import sys
s = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
blank = [(i,j) for i in range(9) for j in range(9) if s[i][j] == 0]

def check(x, y):
    num = [i for i in range(1, 10)]

    for i in range(9):
        if s[x][i] in num:
            num.remove(s[x][i])
        if s[i][y] in num:
            num.remove(s[i][y])

    nx, ny = x//3*3, y//3 *3
    for i in range(3):
        for j in range(3):
            if s[nx+i][ny+j] in num:
                num.remove(s[nx+i][ny+j])

    return num

def dfs(idx):
    if idx == len(blank):
        for i in range(9):
            print(*s[i])
        exit(0)

    x, y = blank[idx]
    candi = check(x, y)

    for c in candi:
        s[x][y] = c
        dfs(idx + 1)
        s[x][y] = 0

dfs(0)