[백준/2580] 스도쿠 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

def col(x, n):
    for i in range(9):
        if n == graph[x][i]:
            return False
    return True

def row(y, n):
    for i in range(9):
        if n == graph[i][y]:
            return False
    return True

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

def dfs(idx):
    if idx == len(blank): # 마지막 0까지 다 채웠을 경우 
        for i in range(9):
            print(*graph[i])
        exit(0)

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

        if col(x, i) and row(y, i) and rect(x, y, i):
            graph[x][y] = i
            dfs(idx + 1) # 다음 0으로 넘어감
            graph[x][y] = 0 # 초기화 (정답이 없을 경우를 대비)

graph = []
blank = []

for i in range(9):
    graph.append(list(map(int, input().split())))

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

dfs(0)

---

✔ 설명

먼저 스도쿠는 해당 빈칸을 채우기 위해 3가지 조건을 확인해야한다.

 

1. 빈칸의 행

2. 빈칸의 열

3. 3x3 정사각형

 

1,2,3 번을 모두 만족하며 1~9의 숫자 중 없는 숫자를 채워넣는 것이 스도쿠이다.

위 조건에 따라 col, row, rect 함수를 만들어 3가지 조건을 확인할 수 있다.

 

먼저 blank 배열에 빈 칸의 좌표를 저장한다.

dfs 함수를 통해 위의 세 조건을 만족하는 숫자들을 넣는다.

 

idx는 blank의 인덱스를 나타내기 위함이다.

따라서 if idx == len(blank)일 경우 정답을 출력하게 된다. (idx는 0부터 blank의 길이만큼 for문을 돌면서 0 빈칸을 채우기 때문이다)

---

✔ 후기

맨 처음엔 col, row 함수의 리턴 값을 True, False로 생각하지 않고 1~9까지 있는 배열에서 없는 값만 골라 return 해주는 걸로 구현했었다. 이렇게 구현하다보니 받은 값으로 다시 백트래킹을 구현해야하는 과정이 복잡해졌다고 느껴서 다른 코드를 참고했다. 3x3 스도쿠를 검사하는 과정은 어떻게 nx, ny 값을 구할 수 있는지 잘 알지 못했다.

조건 3개 함수를 구현한 후에는 dfs로 구현하면 된다. 조건 함수를 구현하는게 조금 까탈스러웠지 dfs는 재밌었다 (^▽^)/ ʸᵉᔆᵎ