[BOJ] 2239번 : 스도쿠(백트래킹)

목차

접근

스도쿠를 풀어내는 문제다.

스도쿠 문제는 N과M 문제와 더불어서 백트래킹으로 푸는 가장 대표적인 예제 중 하나이다.

DFS를 수행하면서, 특정 조건을 만족하는지 체크하고 DFS가 끝나면, 다시 원래 상태로 되돌려놓는 알고리즘이다.

이렇게 DFS 알고리즘 시작단에 끝나는 조건을 명시해주면, 특정 조건이 맞는 케이스일 때까지 전체적으로 탐색을 진행할 것이다.

 

해결

백트래킹으로 해결하자.

0인 위치를 먼저 기록해두고, 0인 위치를 하나씩 채워나가는 방식으로 구현을 진행하자.

또한 스도쿠의 정답이 여러개가 나올 수 있음으로 종료단에, return이 아닌 exit를 이용해서 한번만 출력하고 프로그램을 종료시켜줘야한다. 안그럼 출력 초과가 뜬다..

 

코드

sdoku = []
zero_idx = []
for i in range(9):
    tmp = []
    for j, v in enumerate(input()):
        tmp.append(int(v))
        if not int(v):
            zero_idx.append((i, j))
    
    sdoku.append(tmp)
    
def validate_sdoku(i, j, num):
    global sdoku
    # 행, 열 스도쿠  체크
    for k in range(9):
        if sdoku[i][k] == num: # 해당 행에 이미 들어있는 숫자면
            return False
        if sdoku[k][j] == num: # 해당 열에 이미 들어있는 숫자면
            return False
    
    # 스퀘어 스도쿠 체크
    st_row = (i // 3) * 3
    st_col = (j // 3) * 3
    
    for k in range(3):
        for l in range(3):
            if sdoku[st_row + k][st_col + l] == num: # 해당 숫자가 속한 3x3 스퀘어에 이미 있는 숫자면
                return False
            
    return True


def dfs(idx):
    global sdoku, zero_idx
    if idx == len(zero_idx):
        for row in sdoku:
            print(*row, sep="")
        exit(0)
    
    r, c = zero_idx[idx]
    for num in range(1, 10):
        if validate_sdoku(r, c, num):
            sdoku[r][c] = num
            dfs(idx+1)
            sdoku[r][c] = 0
            

dfs(0)