[BaekJoon] 2580 스도쿠

yunan·2020년 9월 28일

백준

🐬 알고리즘 풀이 🐬

목록 보기

13/74

🔦 문제 링크

✍️ 풀이

배열에서 값을 정해야하는 위치를 zero에 기록해둔다.
DFS를 이용해 가능한 경우의 수를 백트래킹으로 따져본다.
작은 사각형의 시작 지점을 찾는 것이 중요하다 -> (x//3 * 3)

<검사 조건>
1. 가로 줄에 없는 숫자 확인
2. 세로 줄에 없는 숫자 확인
3. 현재 위치의 작은 사각형안에 없는 숫자 확인

🛠 코드

import sys


def solve(index):
    if index == len(zero):
        for com in arr:
            for c in com:
                print(c, end=" ")
            print()
        sys.exit(0)
    sel = zero[index]
    x = sel[0]; y = sel[1]
    # 가로 세로

    for val in range(1, 10):
        flag = True
        if val in arr[x]:
            continue
        for k in range(9):
            if arr[k][y] == val:
                flag = False
                break
        if flag is False:
            continue

        for i in range(3):
            for j in range(3):
                start_x = int((x//3)*3); start_y = int((y//3)*3)
                if val == arr[start_x + i][start_y + j]:
                    flag = False
                    continue
        if flag is True:
            arr[x][y] = val
            solve(index+1)
            arr[x][y] = 0


arr = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(9)]
zero = []
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            zero.append((i, j))
solve(0)

✍️ 다른 사람 풀이

각 조건을 함수 형태로 구성해 깔끔하게 풀었다.

🛠 다른 사람 코드

def horizontal(y, n):
    if n in sudoku[y]:
        return False
    return True


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


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


def possible(loc, n):
    return horizontal(loc[0],n) and vertical(loc[1],n) and bythree(loc[0],loc[1],n)

def DFS(index):
    if len(zeros) == index:
        for r in sudoku:
            for k in r:
                print(k, end=" ")
            print()
        exit(0)
    else:
        for i in range(1, 10):
            loc = zeros[index]
            y = loc[0]
            x = loc[1]
            if possible(loc, i):
                sudoku[y][x] = i
                DFS(index + 1)
                sudoku[y][x] = 0


sudoku = [list(map(int, input().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]
DFS(0)