[백준] 2580 스도쿠

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

2580번: 스도쿠

 

<코드>

from sys import stdin
arr = [list(map(int,stdin.readline().split())) for _ in range(9)]
change = []
flag = False

# 0을 찾자
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            change.append((i,j))

def checkrow(r, n):
    for num in arr[r]:
        if n == num:
            return False
    return True

def checkcol(c, n):
    for i in range(9):
        if n == arr[i][c]:
            return False
    return True

def checksquare(r, c, n):
    nr = r//3 * 3
    nc = c//3 * 3
    for i in range(nr, nr+3):
        for j in range(nc, nc+3):
            if n == arr[i][j]:
                return False
    return True

def dfs(idx):
    global flag
    if flag:
        return

    if idx == len(change):
        for row in arr:
            print(*row)
        flag = True
        return

    r = change[idx][0]
    c = change[idx][1]
    for n in range(1, 10):
        if checkrow(r, n) and checkcol(c, n) and checksquare(r, c, n):
            arr[r][c] = n
            dfs(idx+1)
            arr[r][c] = 0
    return

dfs(0)

 

<풀이방법>

1. 바꿔야하는 숫자인 0의 r,c 값 찾아서 리스트에 넣어준다.
2. 1부터 9까지의 숫자 중에 들어갈 수 있는 숫자를 찾아야 하므로 1~9를 for로 돌려서 row, col, square 3가지 경우의 그 숫자가 들어갈 수 있으면 True를 반환
3. 뒤에서 답을 찾을 수 없으면 앞에 넣은 숫자를 초기화 시켜준다.
4. 답을 찾았을 경우 flag를 True로 한다.