[백준 2580] 스도쿠- python (solved.ac - 골드 4)

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

2580번: 스도쿠

풀이

문제를 보았을때 알수있는 힌트

문제를 보고 0인 위치에 숫자를 대입하는 형식으로 풀면 되겠다 라는 생각이 들었다. 

숫자를 넣기전에 넣어도 되는 위치인지 아닌지만 확인하면 끝이 나지 않을까 생각하였다.

백트래킹, bfs로 풀면 문제는 어렵지 않게 풀린다.

 

import sys

input = sys.stdin.readline

graph = [list(map(int,input().split())) for _ in range(9)]
n_list = []
for y in range(9):
    for x in range(9):
        if graph[y][x]==0:
            n_list.append([y,x])
# print(n_list)

def check(x,y,a):
    for i in range(9):
        if graph[y][i]==a:
            return False
        if graph[i][x]==a:
            return False
    nx = x//3*3
    ny = y//3*3
    for i in range(3):
        for j in range(3):
            if a == graph[ny+i][nx+j]:
                return False
    return True
    
def dfs(idx):
    if idx == len(n_list):
        for i in range(9):
            print(*graph[i])
        # return
        exit(0)
    for i in range(1,10):
        y,x = n_list[idx]
        # check 할 필요있음.
        if check(x,y,i):
            graph[y][x]=i
            dfs(idx+1)
            graph[y][x]=0
dfs(0)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2580.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리