[알고리즘] 백준 2580 스도쿠 / pyhton, 백트랙킹

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

2580번: 스도쿠

 

✔ 풀이과정

스도쿠 규칙은 같은 행, 같은 열, 같은 3x3사각형 내에 1~9사이의 숫자가 겹치지 않게 배치하는 것이다.

이걸 시간초과가 나지 않게 확인하기 위해서 c1, c2, c3의 이차원 배열을 만들어서 0~8행열사각형에 1~9숫자가 존재하는지 직관적으로 체크해놓고 스도쿠 전체를 돌면서 규칙에 맞는지 확인한다.

스도쿠 이차원 배열을 돌때는 좌표값이 아닌 0, 1, 2, ...80 까지의 순서값으로 돈다.

 

1행에 숫자 3이 있다면 (0, 3)을 True로 바꾼다. 순서값을 9로 나누면 행좌표값이 나온다.

 

1열에 숫자 3이 있다면 (0, 3)을 True로 바꾼다. 순서값을 9로 나눈 나머지로 바꾸면 열좌표값이 나온다.

 

 

스도쿠에는 3x3사각형이 9개 있다. 0~9로 번호를 매기는 방법은 x, y좌표로 (x//3)*3 + y//3을 계산하면 된다. 첫번째 사각형에 숫자 3이 있다면 (0, 3)을 True로 바꾼다.

 

def squre(x, y):
    return (x//3)*3 + y//3

def dfs(n):
    if n == 81:
        for i in B:
            print(' '.join(map(str, i)))
        return True
    x = n // 9
    y = n % 9
    if B[x][y] != 0:
        return dfs(n+1)
    else:
        for i in range(1, 10):
            if c1[x][i] == False and c2[y][i] == False and c3[squre(x, y)][i] == False:
                c1[x][i] = c2[y][i] = c3[squre(x, y)][i] = True
                B[x][y] = i
                if dfs(n+1):
                    return True
                B[x][y] = 0
                c1[x][i] = c2[y][i] = c3[squre(x, y)][i] = False
    return False

B = [list(map(int, input().split())) for _ in range(9)]
c1 = [[False]*10 for _ in range(9)]
c2 = [[False]*10 for _ in range(9)]
c3 = [[False]*10 for _ in range(9)]
for i in range(9):
    for j in range(9):
        if B[i][j] != 0:
            c1[i][B[i][j]] = True
            c2[j][B[i][j]] = True
            c3[squre(i, j)][B[i][j]] = True
dfs(0)