[백준2580] 스토쿠

문제

---

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

2580번: 스도쿠

 

생각의 흐름

---

사실 이 문제는 브루트 포스 알고리즘이라기보단 백트래킹 알고리즘을 사용한다고 보는 것이 맞다.

zero리스트에는 0의 위치정보를 담은 튜플은 저장한다. 세 개의 함수 horizontal, vertical, bythree는 각각 가로, 세로, 3x3사각형 안에서 val이라는 특정 숫자가 들어가는 것이 유효한지 아닌지를 return한다.  

아래 코드에서 DFS 함수 내의 else 문 부분이 바로 백트래킹을 사용한다. for문을 사용해 1부터 9까지의 숫자를 모두 넣어보고 해당 수가 그 자리에 오는 것이 아니었다면 다시 0으로 만들어줌으로써 백트래킹 기법을 사용하였다.

 

코드

---

# 백준 2580
import sys

def horizontal(x,val):
    if val in sdk[x]:
        return False
    return True

def vertical(y,val):
    for i in range(9):
        if val==sdk[i][y]:
            return False
    return True

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


def DFS(index):
    if index==len(zero):
        for i in range(9):
            for j in sdk[i]:
                print(j,end=' ')
            print()
        sys.exit()
    else:
        nx = zero[index][0]
        ny = zero[index][1]
        for i in range(1,10):
            if horizontal(nx,i) and vertical(ny,i) and bythree(nx,ny,i):
                sdk[nx][ny]=i
                DFS(index+1)
                sdk[nx][ny]=0

sdk = [list(map(int, input().split())) for _ in range(9)]
zero = [(x, y) for x in range(9) for y in range(9) if sdk[x][y]==0]
DFS(0)