[Python] 백준 2239번: 스도쿠

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

2239번: 스도쿠

 

import sys
input = sys.stdin.readline


def getZeroPositions():
    zeroPositions = []

    for i in range(9):
        for j in range(9):
            if nums[i][j] == 0:
                zeroPositions.append((i, j))

    return zeroPositions


def dfs(zeroIndex):
    if zeroLength <= zeroIndex:
        return True

    x, y = zeroPositions[zeroIndex]
    isAvailableNumbers = getIsAvailableNumbers(x, y)

    for n in range(1, 10):
        if isAvailableNumbers[n]:
            nums[x][y] = n
            if dfs(zeroIndex + 1):
                return True
            nums[x][y] = 0

    return False


def getIsAvailableNumbers(x, y):
    isAvailableNumbers = [True]*10

    sectorX = x//3
    sectorY = y//3

    # Sector
    for i in range(3):
        for j in range(3):
            isAvailableNumbers[nums[sectorX*3 + i][sectorY*3 + j]] = False

    # 가로
    for i in range(9):
        isAvailableNumbers[nums[i][y]] = False

    # 세로
    for j in range(9):
        isAvailableNumbers[nums[x][j]] = False

    return isAvailableNumbers


if __name__ == '__main__':
    # 입력
    nums = []
    for _ in range(9):
        curNums = []
        for c in input().rstrip():
            curNums.append(int(c))
        nums.append(curNums)

    # 메인 로직
    zeroPositions = getZeroPositions()
    zeroLength = len(zeroPositions)

    dfs(0)

    # 출력
    for i in range(9):
        for j in range(9):
            print(nums[i][j], end="")
        print()

 

DFS를 통해 이 문제를 풀 것이다.

DFS로 탐색을 하기 전에, zeroPositions라는 리스트에, 0들의 (x, y) 포지션들을 저장할 것이며, 이것은 getZeroPositions()을 통해 수행된다.

 

이후 DFS를 수행한다. 우선 탐색의 진행 방향은 zeroPositions를 따른다. 인자에 zeroIndex를 넣어서, 방금 얻었던 zeroPositions에 접근할 것이다. dfs()를 진행하면서 이 인자를 1씩 증가시킬 것이고, 결국 zeroIndex가 값을 넘어가게 되면(즉, 모든 zeroPositions에 대해 탐색을 진행했다면) True를 리턴하여 재귀 함수들에서 탈출하게 된다.

다음은 dfs()의 세부적인 코드들에 대한 설명이다. 우선 zeroIndex로 현재 탐색 진행 중인 0의 포지션을 x, y에 넣어준다. 이후 getIsAvailableNumbers()라는 함수를 호출하는데, 이 함수는 특정 0의 좌표를 기준으로, 스도쿠 룰에 의거하여 각각의 숫자가 가능한 수인지를 True/False로 구분짓는 리스트를 반환한다. 즉, 예시 입력 1에서 (0, 1)에 해당하는 0에서 가능한 값이 2, 4, 7, 8이므로 isAvailableNumbers는 아래와 같은 리스트를 담는다.

이제 우리는 현재 탐색하는 0에서 가능한 숫자들의 정보를 알고 있다. 다음은 이에 따라서 모든 가능한 숫자들에 대해서 탐색하는 것이다. 여기서 백트래킹을 해주고, dfs()을, zeroIndex+1을 넣어서 돌려주면 된다. 다만 dfs가 if문에 걸려있는 것은, 처음으로 스도쿠가 완성되었을 때(이 때 사전순서상 가장 앞이다.) True를 반환해주기 때문에, 이것을 감지하여 곧바로 재귀에서 탈출하기 위함이다. 이렇게 되면, 백트래킹으로 값이 0으로 복원되기 전에 재귀를 탈출하게 되므로, 탈출 완료 시의 nums가 바로 우리가 원하는 값이 된다. 마지막으로 nums를 형식에 맞게 출력해주면 된다.