[백준 2239번] 스도쿠

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

import sys

input = sys.stdin.readline

# 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에
# 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다

# 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성

# 9개의 줄에 9개의 숫자로 보드가 입력된다. 
# 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

# 9개의 줄에 9개의 숫자로 답을 출력
# 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력
# 즉, 81자리의 수가 제일 작은 경우를 출력한다.

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

row_sets = [set() for _ in range(9)]
col_sets = [set() for _ in range(9)]
area_sets = [set() for _ in range(9)]

zero_list = []

count = 0

for i in range(9):
    for j in range(9):
        if area[i][j] != 0:
            count += 1
            row_sets[i].add(area[i][j])
            col_sets[j].add(area[i][j])

            if 0 <= i <= 2:
                if 0 <= j <= 2:
                    area_sets[0].add(area[i][j])
                elif 3 <= j <= 5:
                    area_sets[1].add(area[i][j])
                elif 6 <= j <= 8:
                    area_sets[2].add(area[i][j])
            elif 3 <= i <= 5:
                if 0 <= j <= 2:
                    area_sets[3].add(area[i][j])
                elif 3 <= j <= 5:
                    area_sets[4].add(area[i][j])
                elif 6 <= j <= 8:
                    area_sets[5].add(area[i][j])
            elif 6 <= i <= 8:
                if 0 <= j <= 2:
                    area_sets[6].add(area[i][j])
                elif 3 <= j <= 5:
                    area_sets[7].add(area[i][j])
                elif 6 <= j <= 8:
                    area_sets[8].add(area[i][j])

        else:
            zero_list.append((i,j))


def get_area_index(i,j):
    if 0 <= i <= 2:
        if 0 <= j <= 2:
            return 0
        elif 3 <= j <= 5:
            return 1
        elif 6 <= j <= 8:
            return 2
    elif 3 <= i <= 5:
        if 0 <= j <= 2:
            return 3
        elif 3 <= j <= 5:
            return 4
        elif 6 <= j <= 8:
            return 5
    elif 6 <= i <= 8:
        if 0 <= j <= 2:
            return 6
        elif 3 <= j <= 5:
            return 7
        elif 6 <= j <= 8:
            return 8
        
def dfs(index):
    
    if index == len(zero_list):
        for i in range(9):
            for j in range(9):
                print(area[i][j], end="")
            print()
        exit()
    
    x, y = zero_list[index]

    for i in range(1,10):
        if i not in row_sets[x] and i not in col_sets[y] and i not in area_sets[get_area_index(x,y)]:
            area[x][y] = i
            row_sets[x].add(i)
            col_sets[y].add(i)
            area_sets[get_area_index(x,y)].add(i)
            dfs(index+1)
            row_sets[x].remove(i)
            col_sets[y].remove(i)
            area_sets[get_area_index(x,y)].remove(i)    
            area[x][y] = 0

dfs(0)

 

이번 문제는 미완성된 스도쿠를 가지고 스도쿠를 완성시키는 문제이다.

 

# 오답 코드
def dfs(remain):

    global area
    
    if remain >= 81:
        for a in area:
            print(a)
        exit()
    
    for i in range(9):
        for j in range(9):
            if area[i][j] == 0:
                flag = False
                for k in range(9,0,-1):
                    if k not in row_sets[i] and k not in col_sets[j] and k not in area_sets[get_area_index(i,j)]:
                        flag = True
                        area[i][j] = k
                        row_sets[i].add(k)
                        col_sets[j].add(k)
                        area_sets[get_area_index(i,j)].add(k)
                        
                        dfs(remain+1)
                        
                        row_sets[i].remove(k)
                        col_sets[j].remove(k)
                        area_sets[get_area_index(i,j)].remove(k)                  
                        area[i][j] = 0
 
                if not flag:
                    return False
    return True

dfs(count)

 

처음에는 남아있는 스도쿠 개수를 DFS 함수의 파라미터로 사용해서 매 재귀마다 2차원 배열을 순회하여 비어있을 경우 1부터 9까지 탐색해보는 방식으로 구현하였는데, 이 방식으로 구현하면 최악의 경우 (81*9)^k 의 시간복잡도를 가지게 되어 어마어마한 시간이 걸리게 된다.

 

다른 분의 풀이를 참고해본 결과, 매 재귀마다 2차원 배열을 돌아가며 빈 자리를 채울 필요 없이, 처음부터 빈 자리들의 좌표를 배열에 저장해준 뒤에 배열의 첫번째 인덱스부터 차근차근 완전탐색 + 백트래킹 해주면 되는 문제였다.

 

배운 점 및 느낀 점

1. 완전탐색을 해야하는 문제인 경우 DFS 함수 내부의 로직이 복잡할수록 시간복잡도가 기하급수적으로 늘어나기 때문에 불필요한 연산을 줄이기 위한 아이디어를 떠올린 뒤에 로직을 구현하자.
2. 배열과 인덱스를 활용하여 완전탐색하는 방법도 활용해보자 !