[Baekjoon]백준 2580 스도쿠(골드 4) - Python

문제설명 1

문제설명 2

문제설명 3

문제를 읽어보면 스도쿠 문제를 해결하여 빈 칸을 채운 후의 결과를 출력하는 문제이다

스도쿠 게임을 안 해본 사람들을 위해 규칙을 간단하게 설명하자면 각 행, 열이1부터 9까지의 숫자로 이루어져있으며

서로 숫자가 겹쳐서는 안 된다 또한 하나의 작은 사각형(3x3)안에서도 해당 규칙을 지켜야한다

제일 처음 문제를 해결하기 위해 들었던 생각으로는 0이 존재할 때 해당 위치의 가로줄 세로줄을 확인한다

확인하여 0이 하나인 곳이 한 곳이라도 존재한다면 그 줄을 확인하여 해당 칸에 숫자를 채우는 방식을 생각하였다

하지만 이렇게 작성을 하면 0을 발견한 위치에서 몇 개인지 count를 해야하고 

for문과 if문을 중첩적으로 작성이 되어 더 좋은 방법을 생각해보았다

 

결론적으로 정답을 확인할 수 있었던 로직은 0의 index값을 리스트로 저장하여 백트래킹 방식으로 해결하는 것이었다

def check_square(x, y, t):
    for i in range(x, x + 3):
        for j in range(y, y + 3):
            if t == sudoku[i][j]:
                return False
    return True

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

def checK_col(y, t):
    for i in range(9):
        if t == sudoku[i][y]:
            return False
    return True

def sol(idx):
    if idx == len(zero_idx):
        for i in sudoku:
            print(*i)
        exit()
    x, y = zero_idx[idx]
    for t in range(1, 10):
        if check_square(x - x % 3, y - y % 3, t) and check_row(x, t) and checK_col(y, t):
            sudoku[x][y] = t 
            sol(idx + 1)
            sudoku[x][y] = 0
    

sudoku = []
for _ in range(9):
    ls = list(map(int, input().split()))
    sudoku.append(ls)

zero_idx = []
for x in range(9):
    for y in range(9):
        if sudoku[x][y] == 0:
            zero_idx.append((x, y))
sol(0)

check_square 함수를 만들어 해당 사각형에 값(t)이 존재하는지 확인하여 존재한다면 False를 반환한다

그 말인 즉슨 그 index에는 값(t)이 들어갈 수 없다는 뜻이다

check_row함수는 해당 행을 확인하여 값이 존재하는지 확인하며, check_col은 열을 확인하는 함수이다

 

문제해결을 핵심적으로 수행하는 sol함수가 제일 중요한데, 입력받은 값(idx)이 zero_idx의 길이와 동일하다면

해당 코드를 종료한다 zero_idx에는 0이 들어있는 위치가 있으며 idx가 len(zero_idx)와 동일하다는 것은

0이 존재하는 위치에 숫자를 다 넣었다는 뜻이 되기 때문이다

x, y변수에 zero_idx에 저장된 값을 넣어준 뒤에 for문을 통해 1부터 9까지의 숫자를 넣으며 적절한 숫자를 찾는다

미리 만들어둔 세 개의 함수가 모두 True를 반환한다면 해당 위치에 True를 반환하게 만든 값을 넣어주면 된다

이후 sol함수를 다시 호출하여 해당 과정을 반복하면 되며, sudoku[x][y] = 0의 부분은 백트래킹의 핵심이다

이 부분이 존재하기 때문에 현재 경로에서 해결하지 못하더라도 이전 과정으로 돌아갈 수 있게된다

 

아직까지는 백트래킹을 자유롭게 사용하는 것에 어려움이 존재하여 검색을 통해 일부 도움을 받았지만,

로직에 대해 생각하며 많은 것을 배울 수 있었다

※ pypy3로 제출하여야 시간초과가 발생하지 않는다 ※