백준 알고리즘 2580 (스도쿠) - python (재풀이)

백준 알고리즘 2580 (스도쿠) - python

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

2580번: 스도쿠

 

가로, 세로, 3x3 사각형에 모두 1~9의 숫자 하나씩 있는 스도쿠!

 

[문제 풀이]

1.  dfs를 진행

2. _map 에 0이 있는지 체크하면서, 출력해도 되는지의 flag와 0의 좌표를 return 

3. flag == True이면 _map 출력

    이 때, return만 해주면 답이 여러 번 출력될 수 있으므로 완전히 종료 : exit(0)

    (실제로 return만 해서 틀려봤다ㅠㅠㅠ)

4. flag == False이면 0의 좌표에 1~9 값을 대입해본다

5. 대입해도 되는 지 먼저 체크 : 가로, 세로, 3x3 사각형을 기준으로 체크

6. 대입할 값이 조건에 성립하면 대입 후 백트래킹

 

import sys
_map = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]

def is_exist(val, x, y):
    for i in range(9):
        # 가로 세로 검사
        if _map[x][i] == val or _map[i][y] == val:
            return True
        # 네모 검사
        corner_x, corner_y = x // 3, y // 3
        if _map[corner_x * 3 + i // 3][corner_y * 3 + i % 3] == val:
            return True
    return False

def print_map():
    for i in range(9):
        print(' '.join(map(str, _map[i])))
    return

def check_map():
    for i in range(9):
        for j in range(9):
            if not _map[i][j]:  # 0이면
                return False, i, j
    return True, -1, -1  # 0이 없으면

def sudoku():
    # 0이 전체에 있는가, 있다면 x, y 좌표
    flag, x, y = check_map()
    if flag:  # 0이 없다면
        print_map()  # 출력
        exit(0)  # 완전히 끝내야함
    else:  # 0이 있다면
        for val in range(1, 10):  # 대입해볼 1 ~ 9
            if not is_exist(val, x, y):  # 대입 값, 0의 x, y 좌표
                _map[x][y] = val  # 대입
                sudoku()
                _map[x][y] = 0  # back tracking
    return

sudoku()