[BOJ] 2580. 스도쿠

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

2580번: 스도쿠

 

 

1. 해결방법

전형적인 스도쿠 문제이다.
스도쿠 문제를 해결하는 원리만 알면 쉽게 풀 수 있는 문제인데 python3로 제출하면 시간초과가 나왔다. 그렇기에 pypy3로 제출,,,

2차원 배열에서 인덱스 값이 0에 해당하는 인덱스 위치를 zero라는 리스트레 append한다.

dfs 백트래킹을 이용해서 탐색을 해야하는데, 1 ~ 9 까지 for문을 돌고 0인 위치에서 행과 열, 3X3 정사각형에 포함되어있지 않은 숫자를 체크해서 0인 위치에 그 값을 갱신하면 된다.

2차원 리스트가 0이 없어지고 다른 숫자로 갱신될 때까지 진행하고 종료하면 된다.

 

 

2. 정답코드 (pypy3)

 

import sys
input = sys.stdin.readline


maps = [list(map(int, input().split())) for _ in range(9)]

# 0을 찾아서 list에 append
zero = []
for i in range(9):
    for j in range(9):
        if maps[i][j] == 0:
            zero.append((i, j))


# row
def row(y, num):
    for j in range(9):
        if maps[y][j] == num:
            return False
    return True


# col
def col(x, num):
    for j in range(9):
        if maps[j][x] == num:
            return False
    return True


# rect
def rect(y, x, num):
    ny, nx = y // 3 * 3, x // 3 * 3
    for j in range(3):
        for k in range(3):
            if maps[j + ny][k + nx] == num:
                return False
    return True


# dfs
def dfs(idx):
    # 종료 지점
    if idx == len(zero):
        for i in range(9):
            print(*maps[i])
        exit(0)

    for i in range(1, 10):
        y, x = zero[idx][0], zero[idx][1]
        if row(y, i) and col(x, i) and rect(y, x, i):
            maps[y][x] = i
            dfs(idx + 1)
            maps[y][x] = 0

# main
dfs(0)