[백준] 2580번 스도쿠 (파이썬)

< 백준 2580번 스도쿠 - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 먼저 해당 문제에서 요구하는 것은 스도쿠의 규칙과 같다. 고정된 9x9 격자의 하나의 인덱스에 값이 비어있으면 그 인덱스와 같은 열, 같은 행 그리고 3x3 단위로 자른 범위의 작은 격자에 같이 속하는 인덱스들은 1~9의 값들을 각각 가져야한다는 것이다. 그래서 알맞은 값을 넣은 격자를 출력하라는 문제이다.
• 문제에서 요구하는 것이 뭘까? 비어있는 모든 칸에 알맞은 숫자를 넣는 것이다. 비교해야하는 인덱스와 비교하면서 가능하면 값을 넣고 가능하지 않으면 다른 값을 넣는 방식으로 말이다. 해당 인덱스에 들어갈 수 있는 가능한 수 중 가장 짧은 수부터 넣으면 안되나? 그럼 제일 짧은 게 한개의 값을 넣어야만 하는 경우니까 값을 무조건 넣으면 안되나? 넣을 수 있는 값이 제일 적은 경우가 무조건 1개가 아닐수가 있다. 그리고 이런 경우도 생길 수 있다. 어떤 칸에서 1이란 값을 넣었는데 나중에 다른 칸으로 갔는데 그 칸은 무조건 1을 넣어야 하는 칸이었던 것이다. 이 경우엔 다시 아까 그 칸으로 가서 1이 아닌 다른 수를 넣고 해당 칸으로 와서 1을 넣어야하는 것이다.
• 그러니까 비어있는 칸에서 만들 수 있는 모든 경우의 수에서 스도쿠 규칙을 지키면서 값을 넣을 수 있는 경우 하나를 출력하라는 말이다. 이 경우의 수를 구하는 방법은 조합, 순열, 백트래킹 등이 있지만 백트래킹을 이용하는 것이 좋을 것 같다.
• 그 이유는 백트래킹은 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 백트래킹은 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 가기위해서 가지치기를 잘해야 하고 이것에 따라 효율성이 결정된다. 이를 이용하면 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴볼 수 있다.
• 구현할 기능을 정리하겠다. 맨처음 비어있는 인덱스들을 찾고 같은 열, 같은 행, 3x3 격자를 확인하여 해당 인덱스들에 들어갈 수 있는 숫자들을 찾는다. 그 후 백트래킹을 이용해서 찾은 숫자중 들어갈 수 있는 숫자를 찾고 비어있는 인덱스의 개수만큼 숫자들을 찾았다면 출력하고 끝낸다.
• 여기서 중요한 것은 백트래킹을 만들때 가지치기를 위한 조건 설정과 원하는 결과를 찾았을때 반환을 잘해서 잘 끝내야한다. (필자는 반환을 제대로 하지 않아서 가능한 모든 그리드를 출력했었다.)

구현코드

def find(row, col): # 빈 인덱스에 들어갈 수 있는 숫자의 종류를 찾는 함수
    findNum = [0]*10
    for r in range(N): # 같은 열
        if grid[r][col] != 0:
            findNum[grid[r][col]] = 1
    for c in range(M): # 같은 행
        if grid[row][c] != 0:
            findNum[grid[row][c]] = 1
    for i in isRange[row]: # 3x3 격자
        for j in isRange[col]:
            if grid[i][j] != 0:
                findNum[grid[i][j]] = 1
    for index, n in enumerate(findNum[1:]):
        if n == 0:
            numbers[(row, col)].append(index+1)
def isRight(temp, row, col): # 현재 넣은 값이 들어가도 되는 수인지 판별하는 함수
    # 아까 find랑은 다르게 같은 열, 같은 행, 3x3 격자를 다 다른 배열을 이용하여 비교, 여기선 따로따로 1~9가 겹치지 않는지를 봐야하기 때문
    number = [0]*10
    for r in range(N): # 같은 열
        if temp[r][col] != 0:
            if number[temp[r][col]] == 1: return False
            else:
                number[temp[r][col]] = 1
    number = [0] * 10
    for c in range(M): # 같은 행
        if temp[row][c] != 0:
            if number[temp[row][c]] == 1: return False
            else:
                number[temp[row][c]] = 1
    number = [0] * 10
    for i in isRange[row]: # 3x3 격자
        for j in isRange[col]:
            if temp[i][j] != 0:
                if number[temp[i][j]] == 1: return False
                else:
                    number[temp[i][j]] = 1
    return True
def backTracking(arr, graph, number): # 백트래킹 함수
    if number == len(arr): # number가 비어있는 인덱스의 개수와 같아지면 모든 수를 잘 넣었다는 의미.
        for i in range(N): # 출력 구문
            for j in range(M):
                print(graph[i][j], end=" ")
            print()
        return True # True를 반환할 것
    row, col = arr[number]
    for n in numbers[(row, col)]:
        graph[row][col] = n
        if isRight(graph, row, col):
            #temp = [graph[i].copy() for i in range(N)]
            if backTracking(arr, graph, number+1): return True # True가 반환되면 반복이 중단되고 True를 반환
        graph[row][col] = 0
    return False # False가 반환된다는 것은 가지가 뻗어 나가지 못했다는 의미라서 이전 반복문으로 돌아가서 그 다음 수를 넣는 경우를 진행.
if __name__ == "__main__":
    isRange = {0:(0,1,2), 1:(0,1,2), 2:(0,1,2), 3:(3,4,5), 4:(3,4,5), 5:(3,4,5), 6:(6,7,8), 7:(6,7,8), 8:(6,7,8)}
    N, M = 9, 9
    grid = [list(map(int, input().split())) for _ in range(N)]
    numbers = dict()
    blank = []
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 0:
                blank.append((i, j))
                numbers[(i, j)] = []
                find(i, j)
    backTracking(blank, grid, 0)