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

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

2580번: 스도쿠

문제 설명

스도쿠가 주어졌을 때, 빈 칸을 채워 스도쿠를 완성하는 문제이다.

---

풀이 과정

문제를 풀기전에, 스도쿠가 무엇인지에 대해 먼저 알아야 한다.

자세한 설명은 위 백준 문제링크에 나와있지만

9 x 9 맵에서 가로(행)에 1~9까지 모든 숫자가 들어가야 하고 세로(열)에도 1~9까지의 모든 숫자가 들어가야하고

3x3 정사각형에도 1~9까지의 모든 숫자가 들어가야 한다.

 

그래서 맵이 주어졌을 때

첫 번째 빈 칸부터 시작하여 마지막 빈 칸까지 적절한 수를 넣어가며 스도쿠를 완성시켜야 한다.

그래서 DFS + 백트래킹을 통해

첫 번째 칸에 1~9 숫자를 넣어가며 확인하면 된다.

 

풀이 방법은 다음과 같다.

 

① 먼저 문제에서 빈 칸은 0으로 주어지기 때문에

graph의 0인칸의 위치정보(x, y)를 blank 리스트에 넣어준다.

 

② 첫 번째 빈칸에 1~9까지의 수 중 넣을 수 있는 수를 넣는다.

넣을 수 있는 수는 빈칸의 행,열,3x3정사각형에 없는 수임을 확인하자.

확인이 되면 그 빈칸에는 그 수를 넣어준다.

 

③ 그 다음 빈칸에 대해서도 같은 방법을 수행한다.

 

④ 마지막 빈칸까지 채우면 스도쿠를 완성하므로 맵을 출력한다.

 

import sys
graph = []
blank = []

for i in range(9):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

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

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

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

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


def dfs(idx):
    if idx == len(blank):
        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 checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i):
            graph[x][y] = i
            dfs(idx+1)
            graph[x][y] = 0

dfs(0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !